A formal grammar $G=(\Sigma,N,P,\sigma)$ is said to be in Greibach normal form if every production has the following form: $$A\to aW$$ where $A \in N$ (a non-terminal symbol), $a \in \Sigma$ (a terminal symbol), and $W\in N^*$ (a word over $N$ ).

A formal grammar in Greibach normal form is a context-free grammar. Moreover, any context-free language not containing the empty word $\lambda$ can be generated by a grammar in Greibach normal form. And if a context-free language $L$ contains $\lambda$ , then $L$ can be generated by a grammar that is in Greibach normal form, with the addition of the production $\sigma \to \lambda$ .

Let $L$ be a context-free language not containing $\lambda$ , and let $G=(\Sigma,N,P,\sigma)$ be a grammar in Greibach normal form generating $L$ . We construct a PDA $M$ from $G$ based on the following specifications:

1. $M$ has one state $p$ ,
2. the input alphabet of $M$ is $\Sigma$ ,
3. the stack alphabet of $M$ is $N$ ,
4. the initial stack symbol of $M$ is the start symbol $\sigma$ of $G$ ,
5. the start state of $M$ is the only state of $M$ , namely $p$
6. there are no final states,
7. the transition function $T$ of $M$ takes $(p,a,A)$ to the singleton $\lbrace (p,W)\rbrace$ , provided that $A\to aW$ is a production of $G$ . Otherwise, $T(p,a,A)=\varnothing$ .

Bibliography

1

J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).