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