4/21

\begin{frame}{Unrestricted Grammars} \begin{goal}{} What class of grammars corresponds to Turing machines? \end{goal} \pause\bigskip \begin{block}{} An \alert{unrestricted} grammar $G$ contains rules \begin{talign} x \to y \end{talign} where \alert{$x\neq\lambda$}. \end{block} \medskip Note that there is no restriction other than $x$ being non-empty. \pause\bigskip \begin{goal}{Theorem} A language $L$ is generated by an unrestricted grammar\\ \hfill$\iff$ $L$ is accepted by a Turing machine. \end{goal} \end{frame}