For S
cSS
→
, we have
S
B SS
c
→
.
B
c
c → .
Therefore we have G 1 given by
G
S
a b c P S
1 =
′
({ }, { , , }, , )
*
which has P′ given by
S
B SS
B
c
S
a
S
b
c
c
→
→
→
→
(iii) In P′ above, we have
S
B SS
c
→
not in proper form.
Hence we have new variable D 1 and new productions,
S
B D
D
SS
c
→
→
1
1
Therefore the grammar in Chomsky Normal Form (CNF) is G 2
with productions given by
S
B D
D
SS
B
c
S
a
c
c
→
→
→
→
1
1
and
S
b
→ .
2.5.2 Greibach Nor mal Form
In Chomsky’s Normal Form (CNF), restrictions are put on the length of right
sides of a production, whereas in Greibach Normal Form (GNF), restriction
are put on the positions in which terminals and variables can appear.
GNF is useful in simplifying some proofs and making constructions such
as Push Down Automaton (PDA) accepting a CFG.
Definition: A context-free grammar is said to be in Greibach Normal Form
(GNF) if all productions have the form
A ax
→ ,
where a T
x V
∈
∈
and
* .
148
Theory of Automata, Formal Languages and Computation