\begin{frame}{Exercise}

  \begin{exampleblock}{}
    Use the CYK algorithm to check whether $abbb$ is generated by
    \begin{talign}
      S &\to AB &
      A &\to BB \mid a &
      B &\to AB \mid b
    \end{talign}
    We have\vspace{-1ex}
    \begin{talign}
      V_{a} &= \mpause[1]{\{\, A \,\} \quad\text{since $A \to a$}} \\
      V_{b} &= \mpause{\{\, B \,\} \quad\text{since $B \to b$}} \\
      V_{ab} &= \mpause{\{\, X \mid X \to V_a V_b = \{\,AB\,\} \,\}} \mpause{= \{\, S,B \,\}} \\
      V_{bb} &= \mpause{\{\, X \mid X \to \malert{+14}{2}{V_b V_b} = \{\,\malert{+14}{2}{BB}\,\} \,\}} \mpause{= \{\, A \,\}} \\
      V_{abb} &= \mpause{\{\, X \mid X \to V_a V_{bb} \cup V_{ab} V_b = \{\,AA, SB, BB\,\} \,\}} \mpause{= \{\, A \,\}} \\
      V_{bbb} &= \mpause{\{\, X \mid X \to V_b V_{bb} \cup \malert{+8}{2}{V_{bb} V_b} = \{\,BA, \malert{+8}{2}{AB}\,\} \,\}} \mpause{= \{\, S,B \,\}} \\
      V_{abbb} &= \mpause{\{\, X \mid X \to \malert{+4}{2}{V_a V_{bbb}} \cup V_{ab} V_{bb} \cup V_{abb} V_{b} \,\}} \\
               &\mpause{= \{\, X \mid X \to \{\,AS, \malert{+3}{2}{AB}, SA, BA\,\} \,\}} \mpause{= \{\, S,B \,\}}\\[-3.5ex]
    \end{talign}
    \pause[15]
    The word $abbb$ is in the language since $S \in V_{abbb}$\pause\mpause[0]{}:
    \begin{talign}
      \malert{+0}{1}{\underbrace{S}_{abbb}} \!\to\! 
      \mpause{\underbrace{A}_{a}\malert{+1}{1}{\underbrace{B}_{bbb}} \!\to\!}\mpause{}
      \mpause{\underbrace{A}_{a}\malert{+1}{1}{\underbrace{A}_{bb}}\underbrace{B}_{b} \!\to\!}\mpause{}
      \mpause{\underbrace{A}_{a}\underbrace{B}_{b}\underbrace{B}_{b}\underbrace{B}_{b} \!\to^4\!}\mpause{abbb}
    \end{talign}
  \end{exampleblock}
\end{frame}