--- 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}