--- a/slides/slides05.tex	Thu Oct 29 00:25:20 2020 +0000
+++ b/slides/slides05.tex	Fri Oct 30 01:45:03 2020 +0000
@@ -397,7 +397,7 @@
   child {node {$\meta{E}$}
     child[sibling distance=10mm] {node {$\meta{T}$}
       child {node {$\meta{F}$} child {node {2}}}
-      child {node {+}}
+      child {node {*}}
       child {node {$\meta{T}$} child {node {$\meta{F}$} child {node {3}}}}
     }
     child {node {+}}
@@ -475,6 +475,106 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{CYK Algorithm}
+
+Suppose the grammar:
+
+\begin{center}
+\bl{\begin{tabular}{@ {}lcl@ {}}
+$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\
+$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\
+$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\
+$\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
+$\meta{V}$ & $::=$ &  $\texttt{trains}$ 
+\end{tabular}}
+\end{center}
+
+\bl{\texttt{Jeff trains geometry students}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{CYK Algorithm}
+
+\begin{center}
+  \begin{tikzpicture}[scale=1,line width=0.8mm]
+  \draw (-2,0) -- (2,0);
+  \draw (-2,1) -- (2,1);
+  \draw (-2,2) -- (1,2);
+  \draw (-2,3) -- (0,3);
+  \draw (-2,4) -- (-1,4);
+  
+  \draw (0,0) -- (0, 3);
+  \draw (1,0) -- (1, 2);
+  \draw (2,0) -- (2, 1);
+  \draw (-1,0) -- (-1, 4);
+  \draw (-2,0) -- (-2, 4);
+  
+  \draw (-1.5,-0.5) node {\footnotesize{}\texttt{Jeff}}; 
+  \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trains}}; 
+  \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{geometry}}; 
+  \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{students}}; 
+  
+  \draw (-1.5,0.5) node {$N$}; 
+  \draw (-0.5,0.5) node {$N,V$}; 
+  \draw ( 0.5,0.5) node {$N$}; 
+  \draw ( 1.5,0.5) node {$N$}; 
+
+  \draw (-2.4, 3.5) node {$1$}; 
+  \draw (-2.4, 2.5) node {$2$}; 
+  \draw (-2.4, 1.5) node {$3$}; 
+  \draw (-2.4, 0.5) node {$4$}; 
+  \end{tikzpicture}
+  \end{center}
+
+\begin{textblock}{5}(10,10)
+\small\bl{\begin{tabular}{@ {}lcl@ {}}
+$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\
+$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\
+$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\
+            $\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff}$\\
+            & & $\;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
+$\meta{V}$ & $::=$ &  $\texttt{trains}$ 
+\end{tabular}}  
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Chomsky Normal Form}
+
+A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
+
+\bl{\begin{plstx}[margin=0cm]
+: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a\cdot a | b\cdot b | a | b \\
+\end{plstx}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{CYK Algorithm}
+
+
+\begin{itemize}
+\item fastest possible algorithm for recognition problem
+\item runtime is \bl{$O(n^3)$}\bigskip
+\item grammars need to be transformed into CNF
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
 \frametitle{Context Sensitive Grammars}
 
 It is much harder to find out whether a string is parsed
@@ -919,6 +1019,15 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+\begin{frame}[t,fragile]
+\begin{mybox3}{}
+  For CW2, please include '$\backslash$' as a symbol in strings, because
+  the collatz program contains
+  \begin{lstlisting}[language=Scala, numbers=none]
+  write "\n";\end{lstlisting}  
+\end{mybox3}
+\end{frame}
+
 \begin{frame}[t]
 \begin{mybox3}{}
   val (r1s, f1s) = simp(r1)\\