(iii) S
bSb bcb L G
⇒
⇒
∈ ( )
(iv) S
aSa
abSba
abcba L G
⇒
⇒
⇒
∈ ( )
and so on.
Hence the language generated L(G) is given by
L G
wcw w a b
R
( ) {
|
{ , } }
*
=
∈
where w
R = reversal of w
i.e.,
if w a a
a a
n
n
=
−
1 2
1
KK
then w
a a
a a
R
n n
=
−1
2 1
KK
.
Ì Exam ple 2.2.5: Given G = (N, T, P, S) with
N = {E}, S = E, T = {id, +, *, c}
and
P
E
E E
E
E E
E
E
E
id
: .
.
*
.
( )
.
1
2
3
4
→ +
→
→
→
.
Obtain the derivation tree.
Solu tion
Con text-free Grammars
123
a
S
S
S
a
b
b
c
E
E
*
E
E
E
+
id
id
id
⇒ id * id + id
E
E
E
E
(
)
*
id
id
id
E
E
+
⇒ ( id + id) * id