2.2.2 Sentential Form
For a given CFG with productions S
aA A aB B
bB B
a
→
→
→
→
,
,
,
. The
derivation tree is as shown below.
S
aA aaB
aabB
aaba
⇒
⇒
⇒
⇒
The resultant of the derivation tree is the word w = aaba.
This is said to be in “Sentential Form”.
2.2.3 Par tial Der i va tion Tree
In the definition of derivation tree given, if every leaf has a label from
V T
∪ ∪ { }
λ it is said to be “partial derivation tree”.
2.2.4 Right Most/Left Most/Mixed Der i va tion
Consider the grammar G with production
1
2
.
.
S
aSS
S
b
→
→






Now, we have
S
aSS
aaSSS
aabSS
aabaSSS
aababSS
aababbS
a
⇒
⇒
⇒
⇒
⇒
⇒
⇒
1
1
2
1
2
2
2
ababbb
(Left Most Der i va tion)
The sequence fol lowed is “left most der i va tion”, fol low ing “1121222”, giv -
ing “aababbb”.
Con text-free Grammars
119
a
b
S
A
B
B
a
a