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