Greibach normal form
A formal grammar is said to be in Greibach normal form if every production has the following form:
where (a non-terminal symbol), (a terminal symbol), and (a word over ).
A formal grammar in Greibach normal form is a context-free grammar. Moreover, any context-free language not containing the empty word can be generated by a grammar in Greibach normal form. And if a context-free language contains , then can be generated by a grammar that is in Greibach normal form, with the addition of the production .
Let be a context-free language not containing , and let be a grammar in Greibach normal form generating . We construct a PDA from based on the following specifications:
- 1.
has one state ,
- 2.
the input alphabet of is ,
- 3.
the stack alphabet of is ,
- 4.
the initial stack symbol of is the start symbol of ,
- 5.
the start state of is the only state of , namely
- 6.
there are no final states,
- 7.
the transition function of takes to the singleton , provided that is a production of . Otherwise, .
It can be shown that , the language accepted on empty stack, by . If we further define , then accepts . As a result, any context-free language is accepted by some PDA.
References
- 1 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation
to Automata, Addison-Wesley, (1969).