Chapter 6: Context-Free Languages l;l 225
6.5 Consider the following productions:
S ---j aB IbA
A ---j as IbAA Ia
B ---j bS IaBB Ib
For the string aaabbabbba, find
(a) the leftmost derivation,
(b) the rightmost derivation, and
(c) the parse tree.
6.6 Show that the grammar S ---j a IabSb IaAb, A ---j bS IaAAb is ambiguous.
6.7 Show that the grammar S ---j aB Iab, A ---j aAB Ia. B ---j ABb Ib is
ambiguous.
6.8 Show that if we apply Theorem 6.4 first and then Theorem 6.3 to a
grammar G, we may not get a reduced grammar.
6.9 Find a reduced grammar equivalent to the grammar S ---j aAa, A ---j
bBB, B ---j ab, C ---j aBo
6.10 Given the grammar S ---j AB, A ---j a, B ---j C I b, C ---j D, D ---j E,
E ---j a, find an equivalent grammar which is reduced and has no unit
productions.
6.11 Show that for getting an equivalent grammar in the most simplified
form, we have to eliminate unit productions first and then the
redundant symbols.
6.12 Reduce the following grammars to Chomsky normal form:
(a) S ---j lA lOB,
A ---j lAA I05 I0,
B ---j OBB lIS 11
(b) G = ({S}, {a, b, c}, {5 ---j a Ib Ic5S}, S)
(c) 5 ---j abSb I a I aAb,
A ---j bS I aAAb.
6.13 Reduce the grammars given in Exercises 6.1, 6.2, 6.6, 6.7, 6.9, 6.10
to Chomsky normal form.
6.14 Reduce the following grammars to Greibach normal form:
(a) 5 ---j 55, 5 ---j 051 I01
(b) S ---j AB, A ---j BSB, A ---j BE, B ---j aAb, B ---j a, A ---j b
(c) S ---j AO, A ---j OB. B ---j AO, B ---j 1
6.15 Reduce the grammars given in Exercises 6.1, 6.2, 6.6, 6.7, 6.9, 6.10
to Greibach normal form.
6.16 Construct the grammars in Chomsky normal form generating the
following:
(a) {wcw
J
I,v E 0 {a, b}*},
(b) the set of all strings over {a, b} consisting of equal number of a's
and b's,