a cfg is in greibach normal form if the productions are in the following forms −

a → b

a → bd₁…d_n

s → ε

where a, d₁,....,d_n are non-terminals and b is a terminal.

algorithm to convert a cfg into greibach normal form

step 1 − if the start symbol s occurs on some right side, create a new start symbol s’ and a new production s’ → s.

step 2 − remove null productions. (using the null production removal algorithm discussed earlier)

step 3 − remove unit productions. (using the unit production removal algorithm discussed earlier)

step 4 − remove all direct and indirect left-recursion.

step 5 − do proper substitutions of productions to convert it into the proper form of gnf.

problem

convert the following cfg into cnf

s → xy | xn | p

x → mx | m

y → xn | o

solution

here, s does not appear on the right side of any production and there are no unit or null productions in the production rule set. so, we can skip step 1 to step 3.

step 4

now after replacing

x in s → xy | xo | p

with

mx | m

we obtain

s → mxy | my | mxo | mo | p.

and after replacing

x in y → x_n | o

with the right side of

x → mx | m

we obtain

y → mxn | mn | o.

two new productions o → o and p → p are added to the production set and then we came to the final gnf as the following −

s → mxy | my | mxc | mc | p

x → mx | m

y → mxd | md | o

o → o

p → p