DHARMNON-REGULAR GRAMMARS 313Sol. Step 1. Since the grammar is in simplified form also in and CNF so directly switch to
next step.
Step 2. We see that grammar contains none of the productions are of ILR so try to make
ILR production/s i.e., in the production S → A A if A is replaced by S S [∴ A → S S]
then S → S S A and
further substitute b in place of A [∴ A → b) so
S → b A
Now the productions are
S → S S A | b A | a [ILR productions]
A → S S | b [non ILR productions]
Following assumptions are made for ILR productions
S → S α | β 1 | β 2 [where α is S A; β 1 is b A; β 2 is a;]
(S is ILR non terminal)
Step 3. To, remove ILR productions
(+) S → β 1 | β 2 | β 1 R| β 2 R here we assume that R is a new non terminal
(+) R → α | αR
Substitutes the values of α, β 1 and β 2 then we get
S → bA | a | bAR| aR are in GNF and
R → SA | SAR
Thus, we get following productions are in GNF
S → bA | a | bAR| aR
A → b
and modify remaining non GNF productions i.e.
A → SS and R → SA | SAR
In these productions ILR non terminal (S) position is leftmost (on right side), so substi-
tute GNF derived symbols in place of S. Hence we get GNF productions.
A → bA S | a S | bAR S | aR S
R → bA A | a A | bAR A | aR A
R → bA AR | a AR | bAR AR | aR AR.
Step 4. Since, the grammar has no more non GNF production so process stop.
Therefore, grammar has following GNF productions.
S → bA | a | bAR| aR
A → bA S | a S | bAR S | aR S | b
R → bA A | a A | bAR A | aR A
R → bA AR | a AR | bAR AR | aR AR
Example 11.30. Convert the grammar into GNF,
A 1 → A 2 A 3 | a
A 2 → A 3 A 1 | b
A 3 → A 2 A 3 A 2 | a A 2 | c
Sol. Step 1. Given grammar is in simplified form and its productions are of CNF.
Step 2. Examine the productions and we find that if A 2 is replaced by A 3 A 1 [∴ A 2 →
A 3 A 1 ] in the production A 3 → A 2 A 3 A 2 then this production becomes an ILR production i.e.