Ì Exam ple 2.2.3: Given a CFG given by G = (N, T, P, S)
with N = {S}, T = {a, b}, P =
( )
( )
1
2
S
aSb
S
ab
→
→






.
Obtain the derivation tree and the language generated L(G).
Solu tion
S
ab
S
aSb
aabb
S
aSb
aaSbb
aaabbb
a b
ab L G
⇒
⇒
⇒
⇒
⇒
⇒
⇒
∈
3 3
i.e.
i
,
( )
.e.
i.e.
and so on
,
( )
,
( ),
a b
L G
a b
L G
2 2
3 3
∈
∈
Derivation tree is as follows.
Language generated L G
a b n
n n
( ) {
|
}
=
≥1 .
Ì Exam ple 2.2.4: Given a CFG G = (N, T, P, S)
with N = {S}, T = {a, b, c} and P
S
aSa
S
bSb
S
c
=
→
→
→



 



 
( )
( )
( )
1
2
3
.
Obtain the derivation tree and language generated L(G).
Solu tion
(i) S
c c L G
⇒
∈
,
( )
(ii) S
aSa aca L G
⇒
⇒
∈ ( )
122
Theory of Automata, Formal Languages and Computation
a
S
S
a
S
b
b
a
b
S
C
a
S
S
c
a