9/43
\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}