804 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   804   

   805 \mode<presentation>{

   805 

   806 \begin{frame}[c]

   807 \frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}

   808 

   809 All rules must be of the form

   810 

   811 \begin{center}

   812 \bl{$A \rightarrow a$}

   813 \end{center}

   814 

   815 or

   816 

   817 \begin{center}

   818 \bl{$A \rightarrow B\cdot C$}

   819 \end{center}

   820 

   821 

   822 

   823 \end{frame}}

   824 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   825 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   826 \mode<presentation>{

   827 \begin{frame}[c]

   828 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

   829 

   830 

   831 \begin{center}

   832 \bl{\begin{tabular}{@ {}lcl}

   833 $S$ & $\rightarrow$ &  $N\cdot P$ \\

   834 $P$ & $\rightarrow$ &  $V\cdot N$ \\

   835 $N$ & $\rightarrow$ &  $N\cdot N$ \\

   836 $N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

   837 $V$ & $\rightarrow$ &  $\texttt{trains}$ 

   838 \end{tabular}}

   839 \end{center}

   840 

   841 \bl{\texttt{Jeff trains geometry students}}

   842 

   843 \end{frame}}

   844 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   845 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   846 \mode<presentation>{

   847 \begin{frame}[c]

   848 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

   849 

   850 

   851 \begin{itemize}

   852 \item runtime is \bl{$O(n^3)$}\bigskip

   853 \item grammars need to be transferred into CNF

   854 \end{itemize}

   855 

   856 \end{frame}}

   857 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%