Greibach Normal Form - Automata Theory

What is Greibach Normal Form?

Greibach Normal Form of CFL includes in the Productions across the forms −

A → b

A → bD1…Dn

S → ε

where A, D1,....,Dn are non-terminals and b is a terminal.

Algorithm to Convert a CFG into Greibach Normal Form

Step 1 – Let’s create a new start symbol S’ and a new production S’ → S if the start symbol S appears on right side.

Step 2 – Now remove Null productions. (Using the Null production removal algorithm discussed earlier)

Step 3 –Now remove unit productions. (Using the Unit production removal algorithm discussed earlier)

Step 4 – Now you can remove all direct and indirect left-recursion.

Step 5 – Let’s include all substitutions of productions to convert it into the proper form of GNF.

Problem

Do conversion of the following CFG into CNF

S → XY | Xn | p

X → mX | m

Y → Xn | o

Solution

We can skip step 1 to step 3, incase if S does not visible on the right side of any production and no unit or null productions in the production rule set.

Step 4

After replacing

X in S → XY | Xo | p

with

mX | m

We get following

S → mXY | mY | mXo | mo | p.

And after replacing

X in Y → Xn | o

with the right side of

X → mX | m

We get

Y → mXn | mn | o.

Two new productions O → o and P → p are included in the production set and generate the final GNF as the following −

S → mXY | mY | mXC | mC | p

X → mX | m

Y → mXD | mD | o

O → o

P → p

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics