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
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
Get step-by-step solutions from verified subject matter experts
