30/32
\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}