\Sigma, P, S \rangle$, we can construct a restricted attribute-value grammar (R-AVG) $G'$ that simulates grammar $G$. R-AVG $G'$ consists of the same set of nonterminals and terminals as GNF $G$. The productions of R-AVG $G'$ are described by Table \[RulesSim\]. The only two attributes of R-AVG $G'$ are and . R-AVG $G'$ contains $|N| + 1$ atomic values, one atomic value for each nonterminal and the special atomic value \$. The R-AVG $G'$ uses the feature graph to encode a push-down stack, similar to the encoding of a list. The stack will be used to store the nonterminals that still have to be rewritten.

The three syntactic abbreviations below are used to clarify the simulation. We use represent a stack by a Greek letter, or a string of symbols; the top of the stack is the leftmost symbol of the string. Let $x_0$ encode a stack $\gamma$, then the formulas in the abbreviation ${\mbox{\sc push}}(A_0\ldots A_n)$ express that $x_1$ encodes a stack $A_0\ldots A_n\gamma$. Likewise, the formulas in the abbreviation ${\mbox{\sc pop}}(A)$ express that $x_0$ encodes a stack $A\gamma$, and $X_1$ encodes the stack $\gamma$. The abbreviation expresses that $x_0$ encodes an empty stack. $$\begin{aligned}
{\mbox{\sc push}}(A_0\ldots A_n)    &\mbox{stands 