475 

   476 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   477 \begin{frame}[c]

   478 \frametitle{CYK Algorithm}

   479 

   480 Suppose the grammar:

   481 

   482 \begin{center}

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

   484 $\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\

   485 $\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\

   486 $\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\

   487 $\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

   488 $\meta{V}$ & $::=$ &  $\texttt{trains}$ 

   489 \end{tabular}}

   490 \end{center}

   491 

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

   493 

   494 \end{frame}

   495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   496 

   497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   498 \begin{frame}[c]

   499 \frametitle{CYK Algorithm}

   500 

   501 \begin{center}

   502   \begin{tikzpicture}[scale=1,line width=0.8mm]

   503   \draw (-2,0) -- (2,0);

   504   \draw (-2,1) -- (2,1);

   505   \draw (-2,2) -- (1,2);

   506   \draw (-2,3) -- (0,3);

   507   \draw (-2,4) -- (-1,4);

   508   

   509   \draw (0,0) -- (0, 3);

   510   \draw (1,0) -- (1, 2);

   511   \draw (2,0) -- (2, 1);

   512   \draw (-1,0) -- (-1, 4);

   513   \draw (-2,0) -- (-2, 4);

   514   

   515   \draw (-1.5,-0.5) node {\footnotesize{}\texttt{Jeff}}; 

   516   \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trains}}; 

   517   \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{geometry}}; 

   518   \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{students}}; 

   519   

   520   \draw (-1.5,0.5) node {$N$}; 

   521   \draw (-0.5,0.5) node {$N,V$}; 

   522   \draw ( 0.5,0.5) node {$N$}; 

   523   \draw ( 1.5,0.5) node {$N$}; 

   524 

   525   \draw (-2.4, 3.5) node {$1$}; 

   526   \draw (-2.4, 2.5) node {$2$}; 

   527   \draw (-2.4, 1.5) node {$3$}; 

   528   \draw (-2.4, 0.5) node {$4$}; 

   529   \end{tikzpicture}

   530   \end{center}

   531 

   532 \begin{textblock}{5}(10,10)

   533 \small\bl{\begin{tabular}{@ {}lcl@ {}}

   534 $\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\

   535 $\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\

   536 $\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\

   537             $\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff}$\\

   538             & & $\;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

   539 $\meta{V}$ & $::=$ &  $\texttt{trains}$ 

   540 \end{tabular}}  

   541 \end{textblock}

   542 

   543 \end{frame}

   544 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   545 

   546 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   547 \begin{frame}[t]

   548 \frametitle{Chomsky Normal Form}

   549 

   550 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:

   551 

   552 \bl{\begin{plstx}[margin=0cm]

   553 : \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a\cdot a | b\cdot b | a | b \\

   554 \end{plstx}}

   555 

   556 \end{frame}

   557 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   558 

   559 

   560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   561 \begin{frame}[c]

   562 \frametitle{CYK Algorithm}

   563 

   564 

   565 \begin{itemize}

   566 \item fastest possible algorithm for recognition problem

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

   568 \item grammars need to be transformed into CNF

   569 \end{itemize}

   570 

   571 \end{frame}

   572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   573 

   574 

  1022 \begin{frame}[t,fragile]

  1023 \begin{mybox3}{}

  1024   For CW2, please include '$\backslash$' as a symbol in strings, because

  1025   the collatz program contains

  1026   \begin{lstlisting}[language=Scala, numbers=none]

  1027   write "\n";\end{lstlisting}  

  1028 \end{mybox3}

  1029 \end{frame}

  1030