\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}