\begin{frame}{Linear Bounded Automata}
  \begin{block}{}
    A \emph{linear bounded automaton}, short \emph{LBA},\\
    is a \alert{nondeterministic} TM $(Q,\Sigma,\Gamma,\delta,q_0,F)$.
    \medskip
    
    Note that there is \alert{no $\Box$}\,!
    \medskip

    Instead, we have symbols $\alert{\boldsymbol{[}}$ and $\alert{\boldsymbol{]}}$, and
    \begin{itemize}
    \item $\alert{\boldsymbol{[}}$ and $\alert{\boldsymbol{]}}$ are placed around the input word
    \item for every $q\in Q$, $\delta(q,\alert{\boldsymbol{[}}\,)$ is of the form $(q',\alert{\boldsymbol{[}}\,,\alert{R})$
    \item for every $q\in Q$, $\delta(q,\alert{\boldsymbol{]}}\,)$ is of the form $(q',\alert{\boldsymbol{]}}\,,\alert{L})$
    \end{itemize}
  \end{block}
  The head can only move within the bounds of the input word!
  \pause\smallskip

  \begin{goal}{}
    So the memory is restricted by the length of the input word.
  \end{goal}  
  \pause\smallskip

  \begin{block}{}
    The \emph{language $L(M)$ accepted by} LBA $M = (Q,\Sigma,\Gamma,\delta,q_0,F)$ is
    \begin{talign}
      \{\, w \in \Sigma^+ \mid q_0[w]  \vdash^+ [u q v] \;\text{ for some $q \in F, u,v \in \Gamma^*$} \,\}
    \end{talign}
  \end{block}  
\end{frame}