Ì Exam ple 2.2.9: Given a CFG with
P
S
aA
A bS
A b
=
→
→
→



 



 
1
2
3
.
.
.
. Obtain the derivation tree and L(G).
Solu tion
S
aA ab
⇒
⇒
S
aA abS
abaA abab
⇒
⇒
⇒
⇒
K K
The derivation trees suggest ab, abab, ....
Therefore the language generated
L G
ab
n
n
( ) {( ) |
}
=
≥ 1
Ì Exam ple 2.2.10: Obtain the production rules for CFG given the
language generated as
(a) L G
w w a b
w
w
a
b
( ) { |
{ , } ,
( )
( )}
*
=
∈
=
(b) L G
w w a b
w
w
a
b
( ) { |
{ , } ,
( )
( )}
*
=
∈
= 2
(c) L G
w w a b
w
w
a
b
( ) { |
{ , } ,
( )
( )}
*
=
∈
= 3
Solu tion
(a) S
SaSbS
S
S
SbSaS
→
→ ∈
→
(b) S
SaSaSbS
S
SaSbSaS
S
SbSaSaS
S
→
→
→
→ ∈
126
Theory of Automata, Formal Languages and Computation
a
S
b
A
a
S
A
b
S
a
A
b