4. Given grammar G with productions
S
aB bA A a aS bAA B
b bs aBB
→
→
→
| ,
| |
,
| |
.
For the string aaabbabbba, find a rightmost derivation, leftmost
derivation and parse tree.
5. Obtain the derivation tree for the string a
2 b
2 c in the grammar
G
N T P S
= ( , , , ) where N
x x
T
a b c S x
=
=
=
( , ),
( , , ),
0 1
0 ,
P
x
ax bx x
bx c
=
→
→
{
|
,
| }
0
0
1 1
1
.
6. Obtain a CFG that generates the language L a b c i j k
i j k
=
≥
{
| , ,
0 and
either i = j or j = k}. Is the grammar you have generated ambiguous?
7. Let G A and G B be context-free grammars, generating the languages
L(G A ) and L(G B ), respectively. Show that there is a context-free
grammar generating each of the following sets.
(a) L G
L G
A
B
( )
( )
∪
(b) L G L G
A
B
( ) ( ) (c) L G A
( )
* .
8. Given V = {S, A, B, a, b} and T = {a, b}. Determine whether G = (V, T, S,
P) is a type 0 grammar but not a type 1 grammar, a type 1 grammar but
not a type 2 grammar, or a type 2 grammar but not a type 3 grammar if P,
the set of productions is
(a) S
aAB A Bb B
→
→
→
,
,
λ; (b) S
ABa AB
a
→
→
,
;
(c) S
bA A B B
a
→
→
→
,
,
;
(d) S
bA A b S
→
→
→
,
,
λ;
(e) S
aA A bB B
b B
→
→
→
→
,
,
,
.
λ
9. Given G is a grammar with V
a b c S T
a b c
=
=
{ , , , },
{ , , }, starting symbol
S, and productions S
abS
→
, S
bcS
→
, S
bbS
→
, S
a
→ and S
cb
→ .
Construct derivation trees for:
(a) bcbba
(b) bbbcbba
(c) bcabbbbbcb.
10. For a grammar G with productions
S
aAS a
A
SbA SS ba
→
→
|
| | .
Show that S aabbaa
⇒
*
and construct a derivation tree for aabbaa.
11. Obtain a CFG for generating all integers.
12. Given the grammar G:
S
aAD
A aB bAB
B
b
D d
→
→
→
→
|
Reduce the grammar G to Chomsky Normal Form.
Con text-free Grammars
151