Greibach normal 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:
has one state ,
the input alphabet of is ,
the stack alphabet of is ,
the initial stack symbol of is the start symbol of ,
the start state of is the only state of , namely
there are no final states,
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.
|Title||Greibach normal form|
|Date of creation||2013-03-22 18:55:22|
|Last modified on||2013-03-22 18:55:22|
|Last modified by||CWoo (3771)|