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{ \begin{frame}[c] + +``I hate coding. I do not want to look at code.'' + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +``I am appalled. You do not show code anymore.'' + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] \frametitle{\begin{tabular}{c}ReDoS\end{tabular}} \begin{itemize} @@ -348,134 +368,33 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ \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{ -\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{ -\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{ -\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{ \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{ -\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{ \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{ -\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{ -\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{ \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{ +\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{ +\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}