Greibach normal form
A formal grammar $G=(\mathrm{\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 nonterminal symbol), $a\in \mathrm{\Sigma}$ (a terminal symbol), and $W\in {N}^{*}$ (a word over $N$).
A formal grammar in Greibach normal form is a contextfree grammar. Moreover, any contextfree language not containing the empty word $\lambda $ can be generated by a grammar in Greibach normal form. And if a contextfree 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 contextfree language not containing $\lambda $, and let $G=(\mathrm{\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 $\mathrm{\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 $\{(p,W)\}$, provided that $A\to aW$ is a production of $G$. Otherwise, $T(p,a,A)=\mathrm{\varnothing}$.
It can be shown that $L=L(M)$, the language^{} accepted on empty stack, by $M$. If we further define $T(p,\lambda ,\sigma ):=\{(p,\lambda )\}$, then $M$ accepts $L\cup \{\lambda \}$. As a result, any contextfree language is accepted by some PDA.
References
 1 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation^{} to Automata, AddisonWesley, (1969).
Title  Greibach normal form 

Canonical name  GreibachNormalForm 
Date of creation  20130322 18:55:22 
Last modified on  20130322 18:55:22 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Classification  msc 68Q45 
Synonym  GNF 
Related topic  ChomskyNormalForm 
Related topic  KurodaNormalForm 