\begin{frame}{From  LBA's to Context-Sensitive Grammars}
    For every LBA $M$, the language $L(M)$ is context-sensitive.
  \begin{block}{Proof sketch.}
    As before, build an unrestricted grammar $G$ with $L(G) = L(M)$.
    All productions rules are context-sensitive, except for:
      \alert{\Box \to \lambda}
    However, a linear bounded automaton does not use $\Box$\,!\\
    (It never leaves the borders of the input word.)

    Therefore, we can drop
      \item the rule $\Box \to \lambda$\pause, and
      \item the rules $S\to V_\Box^\Box S \mid S V_\Box^\Box$.
    (In step 1, we derive from $S$ 
    a word $V_{q_0[a_1}^{a_1}V_{a_2}^{a_2}\cdots V_{a_{n-1}}^{a_{n-1}}V_{a_n]}^{a_n}$.)