## You are here

HomeGreibach normal form

## Primary tabs

# Greibach normal form

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 $\{(p,W)\}$, provided that $A\to aW$ is a production of $G$. Otherwise, $T(p,a,A)=\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 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).

## Mathematics Subject Classification

68Q42*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections