S
aSS
aSb
aaSSb
aabSb
aabaSSb
aabaSbb
aabab
⇒
⇒
⇒
⇒
⇒
⇒
⇒
1
2
1
2
1
2
2
bb
(Mixed Der i va tion)
The sequence 1212122 represents a “Mixed Derivation”, giving
“aababbb”.
S
aSS
aSb
aaSSb
aaSaSSb
aaSaSbb
aaSabbb
aab
⇒
⇒
⇒
⇒
⇒
⇒
⇒
1
2
1
1
2
2
2
abbb
(Right Most Der i va tion)
The sequence 1211222 represents a “Right Most Derivation”, giving
“aababbb”.
Ì Exam ple 2.2.1: A grammar G which is context-free has the
productions
S
aAB
A Bba
B
bB
B
c
→
→
→
→ .
(The word w = acbabc is derived as follows)
S
aAB
a Bba B
acbaB
acba bB
acbabc
⇒
→
⇒
⇒
⇒
(
)
( )
.
Obtain the derivation tree.
120
Theory of Automata, Formal Languages and Computation