Question: Let us, for the purposes of this problem only, allow a production of the form N 1 rN 2 where N 1 and N

Let us, for the purposes of this problem only, allow a production of the form

N1 → rN2

where N1 and N2 are nonterminal and r is a regular expression. The meaning of this formula is that in any working string we may substitute for N1 any string wN2, where w is a word in the language defined by r. This can be considered a short hand way of writing an infinite family of productions, one for each word in the language of r.
Let a grammar be called bad if all its productions are of the two forms

N1 → rN2
N3 → Λ

Bad grammars generate languages the same way CFGs do.
Prove that even a bad grammar cannot generate a nonregular language, by showing how to construct one regular expression that defines the same language as the whole bad grammar.

Step by Step Solution

3.30 Rating (174 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock

The proof is by contradiction Suppose that our nonregular language has the same structure as some bad grammar Then the last production of the grammar ... View full answer

blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related SQL Database Programming Questions!