Greibach normal formGreibachNormalForm2009-05-11 22:42:352009-08-08 23:09:20Definitioncontext-free language\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}A formal grammar $G=(\Sigma,N,P,\sigma)$ is said to be in \emph{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:
\begin{enumerate}
\item $M$ has one state $p$,
\item the input alphabet of $M$ is $\Sigma$,
\item the stack alphabet of $M$ is $N$,
\item the initial stack symbol of $M$ is the start symbol $\sigma$ of $G$,
\item the start state of $M$ is the only state of $M$, namely $p$
\item there are no final states,
\item 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$.
\end{enumerate}
It can be shown that $L=L(M)$, the language accepted on empty stack, by $M$. If we further define $T(p,\lambda,\sigma):=\lbrace (p,\lambda)\rbrace$, then $M$ accepts $L\cup \lbrace\lambda\rbrace$. As a result, any context-free language is accepted by some PDA.
\begin{thebibliography}{9}
\bibitem{hu} J.E. Hopcroft, J.D. Ullman, {\em Formal Languages and Their Relation to Automata}, Addison-Wesley, (1969).
\end{thebibliography}