diff -r b17eff695c7f -r 2e9134d25a2b slides/slides06.tex --- a/slides/slides06.tex Mon Nov 11 13:48:34 2013 +0000 +++ b/slides/slides06.tex Mon Nov 11 15:26:20 2013 +0000 @@ -255,7 +255,8 @@ \begin{enumerate} \item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip -\item Replace any nonterminal \bl{$X$} in the string by the right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip +\item Replace any nonterminal \bl{$X$} in the string by the +right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip \item Repeat 2 until there are no nonterminals \end{enumerate} @@ -800,60 +801,8 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}} - -All rules must be of the form - -\begin{center} -\bl{$A \rightarrow a$} -\end{center} - -or - -\begin{center} -\bl{$A \rightarrow B\cdot C$} -\end{center} - - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} - + -\begin{center} -\bl{\begin{tabular}{@ {}lcl} -$S$ & $\rightarrow$ & $N\cdot P$ \\ -$P$ & $\rightarrow$ & $V\cdot N$ \\ -$N$ & $\rightarrow$ & $N\cdot N$ \\ -$N$ & $\rightarrow$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\ -$V$ & $\rightarrow$ & $\texttt{trains}$ -\end{tabular}} -\end{center} - -\bl{\texttt{Jeff trains geometry students}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} - - -\begin{itemize} -\item runtime is \bl{$O(n^3)$}\bigskip -\item grammars need to be transferred into CNF -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}