(c) A
A a
A aB
⇒∈
⇒
⇒
L G
ww
w a b
R
( ) {
|
{ , } }
=
∈
+
(d) S
aS
S
bS
L G
a b
S
→
→
=
→ ∈
( ) { , }
*
Language generated of any string of a,b
(e) S
aS
S
bS
L G
a b a
S a
→
→
=
→
( ) { , }
*
(f) S
ab
S
bS
L G
a b
S a
S
b
→
→
=
→
→
+
( ) { , } .
Ì Exam ple 2.2.8: Given a CFG G = (N, T, P, S)
with N = {S, A}, T = {a, b} and P
S
aS
S
aA
A bA
A b
=
→
→
→
→










1
2
3
4
.
.
.
.
Obtain the derivation tree and L(G).
Solu tion
S
aA ab
S
aS
aaA aab
S
aS
aaS
aaaA aaabA aaabb
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
and so on ...
The derivation tree has been shown here in fig.
The language generated is
L G
a b n
m
n m
( ) {
,
}
=
≥
≥
1
1
Con text-free Grammars
125