and $\gamma = \epsilon$. Then there is a left-most derivation $S \stackrel{n+1}{\Rightarrow}
        \alpha a$. GNF $G$ contains the production $A \rightarrow a$ iff R-AVG $G'$ contains production $A \rightarrow a$ with equation . Hence by the induction hypotheses, there is a derivation $S \stackrel{n+1}{\Rightarrow} \alpha a$ with stack $\$$.

Because every context free language is generated by some GNF $G$, every context free language is generated by some R-AVG $G'$.

Constructing an Honestly Parsable Attribute-Value Grammar {#hpavg}
=========================================================

In this section we show how to add a binary counter to an attribute-value grammar (AVG). This counter enforces the Honest-Parsability Constraint (HPC) upon the AVG. To keep this section legible we sometimes use the attribute-value matrices (AVMs) as descriptions. In Section \[create\], we show how to create a counter for the AVG. In Section \[avg2hpc\] we show how to extend the syntactic rules and the lexicon of the AVG.

Arithmetic by AVGs
------------------

We start with a little bit of arithmetic.

#### Natural numbers.

The AVMs below encode natural numbers in binary notation. The sequences of attributes and in these AVMs encode natural numbers, from least- to most-significant bit. The attribute has value 1 (or 0) if, and only if, it 