Solu tion
Ì Exam ple 2.2.2: A CFG given by productions is
S
a
S
aAS
A bS
→
→
→
,
,
and
Obtain the derivation tree of the word w = abaabaa.
Solu tion
w = abaabaa is derived from S as
S
aAS
a bS S
abaS
aba aAS
abaa bs S
abaabaS
abaab
⇒
⇒
⇒
⇒
⇒
⇒
⇒
( )
(
)
( )
aa
The derivation tree is sketched below.
Con text-free Grammars
121
a
S
A
S
b
S
a
S
a
a
A
b
S
a
a
S
A
B
(a) S
aAB
→
(b) A
Bba
→
a
S
A
B
B
b
a
(c) B →
a
S
A
B
B
b
a
c
(d) B
bB
→
a
S
A
B
B
b
a
c
b
B
(e) B
c
→
a
S
A
B
B
b
a b
c
c