\begin{frame}{Example} \begin{exampleblock}{} Consider the TM with $\Sigma=\{a,b,c\}$, $\Gamma=\Sigma\cup\{\Box\}$, $F=\{q_2\}$ and \begin{talign} \delta(q_0,a) &= (q_0,c,R) & \delta(q_0,c) &= (q_1,b,L) \\ \delta(q_0,b) &= (q_0,b,R) & \delta(q_1,b) &= (q_2,a,R) \end{talign} This TM accepts the language \alert{$L((a+b)^*bc(a+b+c)^*)$}. \end{exampleblock} \pause \begin{exampleblock}{} The resulting grammar is: \pause \begin{talign} S &\to V_\Box^\Box S \mid S V_\Box^\Box \mid T \\[-.25ex] T &\to T V_a^a \mid T V_b^b \mid T V_c^c \mid V_{q_0a}^a\mid V_{q_0b}^b\mid V_{q_0c}^c \end{talign}\vspace{-3ex} \begin{talign} V_{q_0a}^{\alert{\alpha}}V_{\alert{\gamma}}^{\alert{\beta}} &\to V_c^{\alert{\alpha}}V_{q_0\alert{\gamma}}^{\alert{\beta}} & V_{q_2\alert{\gamma}}^{\alert{\alpha}} &\to \alert{\alpha} \\[-.25ex] V_{q_0b}^{\alert{\alpha}}V_{\alert{\gamma}}^{\alert{\beta}} &\to V_b^{\alert{\alpha}}V_{q_0\alert{\gamma}}^{\alert{\beta}} & \alert{\beta} V_{\alert{\gamma}}^{\alert{\alpha}} &\to \alert{\beta \alpha} \\[-.25ex] V_{\alert{\gamma}}^{\alert{\beta}}V_{q_0c}^{\alert{\alpha}} &\to V_{q_1\alert{\gamma}}^{\alert{\beta}}V_b^{\alert{\alpha}} & V_{\alert{\gamma}}^{\alert{\alpha}} \alert{\beta} &\to \alert{\alpha \beta} \\[-.25ex] V_{q_1b}^{\alert{\alpha}}V_{\alert{\gamma}}^{\alert{\beta}} &\to V_a^{\alert{\alpha}}V_{q_2\alert{\gamma}}^{\alert{\beta}} & \Box &\to \lambda \end{talign} with $\alert{\alpha}, \alert{\beta} \in \Sigma\cup\{\Box\}$ and $\alert{\gamma}\in\Gamma$. \pause \structure{Exercise}: derive $abc$. \end{exampleblock} \end{frame}