DHARMNON-REGULAR GRAMMARS 311Now we have the remaining non CNF form productions are
(i)A → XbAA and
(ii)B → XaBB
In (i) we put X in place of AA s.t.
(+) A → XbX and
(+) X → AA are in CNF (–) A → XbAA
In (ii) put R in place of BB s.t.
B → XaR and
R → BB are in CNF (–) B → XaBB
Hence We obtain the final CNF grammar is
S → XaB | XbA
A → XaS | a | XbX
X → AA
B → XbS | b | XaR
R → BB11.11 GREIBACH NORMAL FORM (GNF)
If the grammar consists the productions of the form A → a α where α ∈ (VN)* then grammar is
said to be in greibach normal form. It means if the derived string consists of a terminal fol-
lowed by one/more non-terminals then this form of production is a GNF production.
Immediate Left Recursion (ILR)
The production shown in the Fig. 11.22 where the derived string contains the same non termi-
nal as it derived from on its left most position is an ILR production.
AA® aFig. 11.22[But A ⇒N Aγ where γ ∈ (VT ∪ VN)* is not ILR]
Immediate Right Recursion (IRR)
If the derived string in the production contains the same non terminal as it derived from on its
right most position then production is IRR, i.e.,
A®aA or A®abBA(a)(b)
Fig. 11.23
IRR shown in Fig. 11.23(a) is a GNF production but production shown in Fig. 11.23(b) is
not a GNF production.
So, our objective is to convert the ILR and rest of the IRR production to GNF productions.
l Productions of type ILR can be converted as follows,
Assume A → A a is a given ILR production followed by another known production
A→b in the grammar then remove both productions like as