exists a context free grammar $G'$ in Greibach normal form such that $L=L(G')$. From this grammar $G'$, we can construct a pushdown store $M$ that accepts exactly the words in $L(G')=L$. Such a pushdown store $M$ is actually a finite state automaton $M'$ with a stack $S$. The finite state automaton $M'$ may be simulated by a chain- and $\epsilon$-rule free regular grammar. Furthermore, we can construct an attribute-value language ${\cal A'}(A,V,L)$ that simulates the stack $S$. Thus it should be clear that there exists an R-AVG $G$ that produces word $w$ iff $w \in L(G')$. Details of this construction are deferred to Appendix \[Greib\].

From this we can draw the conclusion that the class of context free languages is indeed a proper subset of the class of R-AVG languages, unless ${\mathord{\it P}}={\mathord{\it NP}}$.

\[PNP\] Let ${\cal C}$ be a recursively presentable class of grammars such that:

1.  $G\in{\cal C}$ can be decided in time polynomial in ${\mathopen|G\mathclose|}$

2.  $G\stackrel{*}{\Rightarrow}w$ can be decided in time polynomial in ${\mathopen|G\mathclose|}+{\mathopen|w\mathclose|}$.

If every R-AVG $G$ has a grammar in ${\cal C}$ then ${\mathord{\it P}}={\mathord{\it NP}}$. In fact, for every language $L$ in ${\mathord{\it NP}}$ there is an explicit deterministic polynomial time algorithm.

Let 