\begin{frame}{Cocke-Younger-Kasami Algorithm (1965)}
  \begin{block}{}
    Let $G$ be a grammar in Chomsky normal form.
    \smallskip
    
    \emph{Goal:} determine whether word $w \ne \lambda$ is in $L(G)$.
    \pause\medskip
    
    \emph{Idea:} compute sets $V_{u}$ of variables ($u$ subword of $w$) such that 
    \begin{talign}
      \alert{V_{u}} = \{\, A\in V \mid A \Rightarrow^+ u \,\} 
    \end{talign}
    \pause
    as follows:
    \begin{itemize}
    \pause
      \item if $|u| = 1$, then $V_{u} = \{\, A \in V \mid A \to u \in P \,\}$
    \pause
      \item if $|u| > 1$, then $V_{u}$ is the set of all $A \in V$ such that
        \begin{itemize}
          \item $u = u_1u_2$ for some non-empty words $u_1,u_2$, and
          \item $A\to BC \in P$ with $B \in V_{u_1}$ and $C\in V_{u_2}$.
        \end{itemize}
    \end{itemize}
    \pause
    Finally, \alert{$w \in L(G)$} $\Leftrightarrow$ \alert{$S\in V_{w}$}.
  \end{block}
  \pause\medskip

  \begin{goal}{}
    \structure{Worst-case time complexity}: $O(n^3)$\\
    (There are $n(n+1)/2$ sets $V_{u}$, and computation of $V_{u}$ is $O(n)$.)
  \end{goal}
\end{frame}