2.1.6 Con ver sion of Left-lin ear Gram mar into
Right-Lin ear Gram mar
Step
Method
(a) Con struct a right-lin ear
grammar for the dif fer ent
languages L
R .
Replace each pro duc tion A x
→ of L
with a pro duc tion A x
R
→
and
replace each pro duc tion A Bx
→
with a pro duc tion A x B
R
→
(b) Con struct an NFA for L
R from
the right-lin ear gram mar. This
NFA should have just one
final state.
Refer to sec tion 2.1.4 for deriv ing an
NFA from a right-lin ear gram mar.
(c) Reverse the NFA for L
R to
obtain an NFA for L.
(i) Con struct an NFA to
recognize the lan guage L.
(ii) Ensure the NFA has only a
sin gle final state
(iii) Reverse the direc tion of arcs
(iv) Make the ini tial state final and
final state ini tial
(d) Con struct a right-lin ear
grammar for L from the
NFA for L.
This is the tech nique described in
the pre vi ous sec tion.
Ì Exam ple 2.1.1: Give some example of context-free languages.
Solu tion
(a) The grammar G = ({S}, {a, b}, S, P) with productions
S
aSa
S
bSb
S
→
→
→
,
,
λ
is context free.
S
aSa aaSaa aabSbaa aabbaa
⇒
⇒
⇒
⇒
Thus we have L a
ww
w a b
R
( ) {
:
{ , } }
*
=
∈
.
This language is context free.
(b) The grammar G, with production rules given by
S
abB
A aaBb
B
bbAa
A
→
→
→
→
,
,
,
λ
is context free.
Con text-free Grammars
117