The language is
L G
ab bbaa bba ba n
n
n
( ) { (
)
( ) :
}
=
≥ 0
Ì Exam ple 2.1.2: Construct right-and left-linear grammars for the
language L a b
n
m
n m
=
≥
≥
{
:
,
}
2
3 .
Solu tion
Right-Linear Grammar:
S
aS
S
aaA
A bA
A bbb
→
→
→
→
Left-Linear Grammar:
S
Abbb
S
Sb
A
Aa
A aa
→
→
→
→
2.2 DERIVATION TREES
A ‘derivation tree’ is an ordered tree which the the nodes are labeled with the
left sides of productions and in which the children of a node represent its
corresponding right sides.
2.2.1 Def i ni tion of a Der i va tion Tree
Let G = (V, T, S, P) be a CFG. An ordered tree is a derivation tree for G iff it
has the following properties:
(i) The root of the derivation tree is S.
(ii) Each and every leaf in the tree has a label from T ∪ { }
λ .
(iii) Each and every interior vertex (a vertex which is no a leaf) has a
label from V.
(iv) If a vertex has label A V
∈ , and its children are labeled (from left to
right) a a
a n
1
2
, , KK , then P must contain a production of the
form
A a a
a n
→ 1 2
, , K K
(v) A leaf labeled λ has no siblings, that is, a vertex with a child
labeled λ can have no other children.
118
Theory of Automata, Formal Languages and Computation