language. , 2(3):113–124, 1956.

J. Earley. An efficient context-free parsing algorithm. , 13(2):94–102, February 1970.

J. Hopcroft and J. Ullman. . Addison Wesley, Reading, MA, 1979.

M. Johnson. , volume 16 of [*CSLI Lecture Notes*]{}. CSLI, Stanford, 1988.

C. Perrault. On the mathematical properties of linguistic theories. , 10(3–4):165–176, 1984.

G. Smolka. Feature-constraint logics for unification grammars. , 12(1):51–87, 1992.

T. Sudkamp. . Addison Wesley, Reading, MA, 1988.

M. Trautwein. Assessing complexity results in feature theories. ILLC Research Report and Technical Notes Series LP-95-01, University of Amsterdam, Amsterdam, 1995. Submitted to the CMP-LG archive.

Simulating a Context Free Grammar in GNF {#Greib}
========================================

A context free grammar (CFG) is a quadruple $\langle N, \Sigma, P, S \rangle$, where $N$ is a set of nonterminals, $\Sigma$ is a set of terminals, $P$ is a set of productions, and $S \in N$ is the start nonterminal. A CFG is in Greibach normalform (GNF) if, and only if, the productions are of one of the following forms, where $a\in\Sigma, A\in N, A_1\ldots A_n \in N\setminus\{S\}$ and $\epsilon$ the empty string (c.f., [@hopcroft.ea:79], [@sudkamp:88]): $$\begin{aligned}
    A &\rightarrow &a\,A_1\ldots A_n    \\
    A &\rightarrow &a   \\
    S &\rightarrow &\epsilon\end{aligned}$$

Given a GNF $G = \langle N, 