% \def\lastedit{2011-10-18 02:12:10 by stolfi}

% ----------------------------------------------------------------------

  For that purpose, we define a grammar $G_{\pll}$ with the same symbols as $G$, but with the 
  productions
    \eqt{eq.rulesEx}{
      \begin{array}{rcl|rcl|rcl}
        \o0 \oR &\to& \oR     & \o1 \oR &\to& \oc \oR       & ~ &~& ~ \\
        \o0 \oa &\to& \oa \o0 & \o1 \oa &\to& \ob \o1       & \oL \oa &\to& \oL \\
        \o0 \ob &\to& \oa \o1 & \o1 \ob &\to& \oc \o0       & \oL \ob &\to& \oL \o1 \\
        \o0 \oc &\to& \ob \o0 & \o1 \oc &\to& \oc \o1       & \oL \oc &\to& \oL \ob \o0
      \end{array}
    }
  Observe that, as in the original grammar $G$, all substitutions in this table 
  preserve the word's value; except for the rules $\o0 \oR \to \oR$
  and $\o1 \oR \to \oc \oR$, which change a value $m$ to $\phi(m)$.

% ----------------------------------------------------------------------

  For that purpose, we introduce two additional delimiter symbols, the \emph{blank digit} 
  `$\ox$' (an element of $\Delta$) and the \emph{null operator} `$\oy$'. By definition, 
  these symbols have no effect on the value of a word; that is,
  $\val{\beta \ox} =\val{\beta \oy} = \val{\beta}$ for any word $\beta$. 
  We replace the substitution table by
    \eqt{eq.rulesEx}{
      \begin{array}{rcl|rcl|rcl|rcl}
        \ox \oR &\to& \oR     & \o0 \oR &\to& \oR     & \o1 \oR &\to& \oc \ox \oR   & ~ &~& ~ \\
        \ox \oa &\to& \oa \ox & \o0 \oa &\to& \oa \o0 & \o1 \oa &\to& \ob \o1       & \oL \oa &\to& \oL       \\
        \ox \ob &\to& \ob \ox & \o0 \ob &\to& \oa \o1 & \o1 \ob &\to& \oc \o0       & \oL \ob &\to& \oL \oa \o1 \\
        \ox \oc &\to& \oc \ox & \o0 \oc &\to& \ob \o0 & \o1 \oc &\to& \oc \o1       & \oL \oc &\to& \oL \ob \o0 \\
        
        \ox \oy &\to& \oy \ox & \o0 \oy &\to& \oy \o0 & \o1 \oy &\to& \oy \o1       & \oL \oy &\to& \oL 
      \end{array}
    }
  Let $G_{\pll}$ be this modified grammar. 
  Observe that, as in the original grammar $G$, all substitutions in this table 
  preserve the word's value; except for the rules $\o0 \oR \to \oR$
  and $\o1 \oR \to \oc \ox \oR$, which change a value $m$ to $\phi(m)$.


% ----------------------------------------------------------------------

  To see why, consider a generic word of the form $\oL \bin{r}
  \sigma \bin{s} \oR$ of such a derivation, where $r$ and $s$ are
  natural numbers, and $\sigma$ is an operator symbol. By induction on
  the length of $\bin{r}$, we can show that an eager derivation from
  this word will eventually yield the operator-free word $\oL
  \bin{t}\bin{s}\oR$, where
    \eqt{eq.arith}{
      t = 
        \left\{
          \begin{array}{ll}
            3r     & \mbox{if $\sigma = \oa$}, \\
            3r+1   & \mbox{if $\sigma = \ob$}, \\
            3r+2   & \mbox{if $\sigma = \oc$}, \\
          \end{array}
        \right.
    }
  Now consider an operator-free word $\oL \bin{n}\oR$. The next (unique)
  eager derivation step uses one of the substitutions from the first row 
  of table~\eqref{eq.rules}, based on the last bit of $[n]$. Namely,
    \eqt{eq.start}{
      \begin{array}{lclcl}
        \oL \bin{2 r}\oR  &=& \oL \bin{r} 0 \oR &\eto& \oL \bin{r}\oR\\
        \oL \bin{2 r+1}\oR &=& \oL \bin{r} 1 \oR &\eto& \oL \bin{r}\oc\oR
      \end{array}
    }
  By the previous observation, the word $\oL \bin{r}\oc\oR$
  will eventually derive to $\oL \bin{3 r + 2}\oR$. 
  It follows that an eager derivation from any word $\enc{m}$ will 
  yield $\enc{\phi(m)}$ as the next operator-free word.
  
% ----------------------------------------------------------------------
  
  In view of this observation, for the study of lazy derivations it is conventient to
  use an expanded variant of the grammar $G$.
  The alphabet of the new grammar $G'$ is the same as that of $G$, plus four additional digits
  $\set{\bzz,\bzu,\buz,\buu}$ that are meant to represent the consecutive 
  digit pairs $\set{00,01,10,11}$, respectively.  The substitution rules are augmented as follows
    \eqt{eq.rules}{
      \begin{array}{rcl|rcl|rcl|rcl|rcl|rcl|rcl}
        0 \oR &\to& \oR   &
        1 \oR &\to& \oc \oR &
        \bzz \oR &\to& \oR &
        \bzu \oR &\to& \ob \oR &
        \buz \oR &\to& \oc \oR &
        \buu \oR &\to& \oc \oc \oR & 
        ~ &~& ~ \\
        0 \oa &\to& \oa 0 &
        1 \oa &\to& \ob 1   &
        \bzz \oa &\to& \oa \bzz &
        \bzu \oa &\to& \oa \buu &
        \buz \oa &\to& \ob \buz &
        \buu \oa &\to& \oc \buu & 
        \oL \oa &\to& \oL     \\
        0 \ob &\to& \oa 1 &
        1 \ob &\to& \oc 0   &
        \bzz \ob &\to& \oa \bzu &
        \bzu \ob &\to& \ob \bzz &
        \buz \ob &\to& \ob \buu &
        \buu \ob &\to& \oc \buz &
        \oL \ob &\to& \oL 1   \\
        0 \oc &\to& \ob 0 &
        1 \oc &\to& \oc 1   &
        \bzz \oc &\to& \oa \buz &
        \bzu \oc &\to& \ob \bzu &
        \buz \oc &\to& \oc \bzz &
        \buu \oc &\to& \oc \buu &
        \oL \oc &\to& \oL \buz \\
      \end{array}
    }
  Let's say that a word $\beta$ is \emph{similar} to $\gamma$ whenever one can be obtained
  from the other by zero or more replacements $\bzz \frto 00, $\bzu \frto 01$, $\buz\frto 10$,
  or $\buu \frto 11$.  Then each substitution rule of $G'$ that involves one of the new digits
  corresponds to two consecutive substitutions of $G$ applied to the similar word of $G$.

  A lazy derivation of $G'$ is defined similarly to one of $G$; that is, at each step
  one should apply the leftmost rule that  

