3. A pure grammar, G, is one which uses no variables in its productions. Such a

Question

3. A pure grammar, G, is one which uses no variables in its productions. Such a grammar is dened by a triple, (T,P,w), where T is a nite set of terminals, P is a nite set of productions T T, and w is the start word. For such a grammar, dene the language generated by G to be the set of all terminal strings derivable from the start word. For example, if G = ({a,b},P,ab) with P dened by a ab,b bab | bb then one deriva- tion would be ab abb ababb abbabb, so L(G) contains the words ab,abb,ababb, and abbabb, among others.

(a) Show that every pure language, L(G), is a CFL by describing how to construct an equivalent CFG, H, from the pure grammar G.

(b) Under what circumstances is L(G) nite, for a pure grammar G?

(c) Bonus. Show that the pure languages are a proper subset of the CFLs by nding a CFL that can’t be generated by a pure grammar.

Explanation / Answer

G=({a,b},P,ab)

Rules

a->ab

b->bab|bb

(a) Converting to CFG G=(T,P,w)

T={a,b}

               Production rule are a->ab ,b->bab|bb

               Derivation

               ab=>abb=>ababb=>abbabb

               Since the production rules are in the form A-> where A N

              And (N U T)* ,the above grammar is a context free grammer

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.