
diff -r d2c6852ca8da -r 7a777d9cc343 slides06.tex
--- a/slides06.tex	Mon Oct 29 12:31:31 2012 +0000
+++ b/slides06.tex	Wed Oct 31 02:05:12 2012 +0000
@@ -219,6 +219,26 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+
+``I hate coding. I do not want to look at code.''
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+``I am appalled. You do not show code anymore.''
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{\begin{tabular}{c}ReDoS\end{tabular}}
 
 \begin{itemize}
@@ -348,134 +368,33 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Last Week\end{tabular}}
 
-Last week I showed you\bigskip
-
-\begin{itemize}
-\item an algorithm for automata minimisation
-
-\item an algorithm for transforming a regular expression into an NFA
-
-\item an algorithm for transforming an NFA into a DFA (subset construction)
-
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}This Week\end{tabular}}
-
-Go over the algorithms again, but with two new things and \ldots\medskip
-
-\begin{itemize}
-\item with the example: what is the regular expression that accepts every string, except those ending 
-in \bl{aa}?\medskip
-
-\item Go over the proof for \bl{$L(rev(r)) = Rev(L(r))$}.\medskip
-
-\item Anything else so far.
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
+\newcommand{\qq}{\mbox{\texttt{"}}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Proofs By Induction\end{tabular}}
+\frametitle{\begin{tabular}{c}Grammars\end{tabular}}
+
+A (context-free) Grammar \bl{$G$} consists of
 
 \begin{itemize}
-\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip
-\item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already
-holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip
-\item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already
-holds for \bl{r$_1$} and \bl{r$_2$}.
-\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already
-holds for \bl{r}.
-\end{itemize}
-
+\item a finite set of nonterminal symbols (upper case)
+\item a finite terminal symbols or tokens (lower case)
+\item a start symbol (which must be a nonterminal)
+\item a set of rules
 \begin{center}
-\bl{$P(r):\;\;L(rev(r)) = Rev(L(r))$}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-
-What is the regular expression that accepts every string, except those ending 
-in \bl{aa}?\pause\bigskip
-
-\begin{center}
-\begin{tabular}{l}
-\bl{(a + b)$^*$ba}\\
-\bl{(a + b)$^*$ab}\\
-\bl{(a + b)$^*$bb}\\\pause
-\bl{a}\\
-\bl{\texttt{""}}
-\end{tabular}
-\end{center}\pause
-
-What are the strings to be avoided?\pause\medskip
-
-\begin{center}
-\bl{(a + b)$^*$aa}
+\bl{$A \rightarrow \text{rhs}$}
 \end{center}
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-
-An NFA for \bl{(a + b)$^*$aa}
-
-\begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \node[state, initial]        (q0) at ( 0,1) {$q_0$};
-  \node[state]                    (q1) at ( 1,1) {$q_1$};
-  \node[state, accepting] (q2) at ( 2,1) {$q_2$};
-  \path[->] (q0) edge node[above] {$a$} (q1)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q0) edge [loop below] node {$a$} ()
-                  (q0) edge [loop above] node {$b$} ()
-            ;
-\end{tikzpicture}
-\end{center}\pause
+where \bl{rhs} are sequences involving terminals and nonterminals.\medskip\pause
 
-Minimisation for DFAs\\
-Subset Construction for NFAs
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}DFA Minimisation\end{tabular}}
-
+We can also allow rules
+\begin{center}
+\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}
+\end{center}
+\end{itemize}
 
-\begin{enumerate}
-\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}
-\item Mark all pairs that accepting and non-accepting states
-\item For  all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether
-\begin{center}
-\bl{($\delta$(q,c), $\delta$(p,c))}
-\end{center} 
-are marked. If yes, then also mark \bl{(q, p)}.
-\item Repeat last step until nothing changed.
-\item All unmarked pairs can be merged.
-\end{enumerate}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -483,141 +402,46 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-
-Minimal DFA \only<1>{\bl{(a + b)$^*$aa}}\only<2->{\alert{not} \bl{(a + b)$^*$aa}}
+\frametitle{\begin{tabular}{c}Palindromes\end{tabular}}
 
 \begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \only<1>{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<2->{\node[state, initial,accepting]        (q0) at ( 0,1) {$q_0$};}
-  \only<1>{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<2->{\node[state,accepting]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
-  \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};}
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-                  (q1) edge[bend left] node[above] {$b$} (q0)
-                  (q2) edge[bend left=50] node[below] {$b$} (q0)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q2) edge [loop right] node {$a$} ()
-                  (q0) edge [loop below] node {$b$} ()
-            ;
-\end{tikzpicture}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ &  $\epsilon$ \\
+$S$ & $\rightarrow$ &  $aSa$ \\
+$S$ & $\rightarrow$ &  $bSb$ \\
+\end{tabular}}
+\end{center}\pause
+
+or
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ &  $\epsilon \;|\; aSa \;|\;bSb$ \\
+\end{tabular}}
 \end{center}
 
-\onslide<3>{How to get from a DFA to a regular expression?}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
 
-\begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-                  (q1) edge[bend left] node[above] {$b$} (q0)
-                  (q2) edge[bend left=50] node[below] {$b$} (q0)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q2) edge [loop right] node {$a$} ()
-                  (q0) edge [loop below] node {$b$} ()
-            ;
-\end{tikzpicture}
-\end{center}\pause\bigskip
-
-\onslide<2->{
-\begin{center}
-\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 +  4\, q_2$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
-
-\end{tabular}
-\end{center}
-}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-                  (q1) edge[bend left] node[above] {$b$} (q0)
-                  (q2) edge[bend left=50] node[below] {$b$} (q0)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q2) edge [loop right] node {$a$} ()
-                  (q0) edge [loop below] node {$b$} ()
-            ;
-\end{tikzpicture}
-\end{center}\bigskip
-
-\onslide<2->{
-\begin{center}
-\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b +  q_2\,b$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
-
-\end{tabular}
-\end{center}
-}
-
-\onslide<3->{
-Arden's Lemma:
-\begin{center}
-If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
-\end{center}
-}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Algorithms on Automata\end{tabular}}
-
-
-\begin{itemize}
-\item Reg $\rightarrow$ NFA: Thompson-McNaughton-Yamada method\medskip
-\item NFA $\rightarrow$ DFA: Subset Construction\medskip
-\item DFA $\rightarrow$ Reg: Brzozowski's Algebraic Method\medskip
-\item DFA minimisation: Hopcrofts Algorithm\medskip
-\item complement DFA
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-\newcommand{\qq}{\mbox{\texttt{"}}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Grammars\end{tabular}}
+\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ &  $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\
-$F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\
-$T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\
+$E$ & $\rightarrow$ &  $num\_token$ \\
+$E$ & $\rightarrow$ &  $E + E$ \\
+$E$ & $\rightarrow$ &  $E - E$ \\
+$E$ & $\rightarrow$ &  $E * E$ \\
+$E$ & $\rightarrow$ &  $( E )$ 
 \end{tabular}}
-\end{center}
+\end{center}\pause
 
-\bl{$E$}, \bl{$F$} and \bl{$T$} are non-terminals\\
-\bl{$E$} is start symbol\\
-\bl{$num$}, \bl{(}, \bl{)}, \bl{+} \ldots are terminals\bigskip\\
-
-
-\bl{\texttt{(2*3)+(3+4)}}
+\bl{\texttt{1 + 2 * 3 + 4}}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -626,32 +450,33 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ &  $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\
-$F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\
-$T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\
+$E$ & $\rightarrow$ &  $F \;|\; F * F$\\
+$F$ & $\rightarrow$ & $T \;|\; T + T \;|\; T - T$\\
+$T$ & $\rightarrow$ & $num\_token \;|\; ( E )$\\
 \end{tabular}}
 \end{center}
 
 \begin{center}
 \begin{tikzpicture}[level distance=8mm, blue]
-  \node {E}
-    child {node {F} 
-     child {node {T} 
-                 child {node {\qq(\qq\,E\,\qq)\qq}
-                            child {node{F \qq*\qq{} F}
-                                  child {node {T} child {node {2}}}
-                                  child {node {T} child {node {3}}} 
+  \node {$E$}
+    child {node {$F$} 
+     child {node {$T$} 
+                 child {node {(\,$E$\,)}
+                            child {node{$F$ *{} $F$}
+                                  child {node {$T$} child {node {2}}}
+                                  child {node {$T$} child {node {3}}} 
                                }
                           }
               }
-     child {node {\qq+\qq}}
-     child {node {T}
-       child {node {\qq(\qq\,E\,\qq)\qq} 
-       child {node {F}
-       child {node {T \qq+\qq{} T}
+     child {node {+}}
+     child {node {$T$}
+       child {node {(\,$E$\,)} 
+       child {node {$F$}
+       child {node {$T$ +{} $T$}
                     child {node {3}}
                     child {node {4}} 
                  }
@@ -660,12 +485,59 @@
 \end{tikzpicture}
 \end{center}
 
-\begin{textblock}{5}(1, 5)
+\begin{textblock}{5}(1, 6.5)
 \bl{\texttt{(2*3)+(3+4)}}
 \end{textblock}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+
+A grammar is \alert{ambiguous} if there is a string that has at least parse trees.
+
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$E$ & $\rightarrow$ &  $num\_token$ \\
+$E$ & $\rightarrow$ &  $E + E$ \\
+$E$ & $\rightarrow$ &  $E - E$ \\
+$E$ & $\rightarrow$ &  $E * E$ \\
+$E$ & $\rightarrow$ &  $( E )$ 
+\end{tabular}}
+\end{center}
+
+\bl{\texttt{1 + 2 * 3 + 4}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\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 BC$}
+\end{center}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 
 \end{document}
 




