# HG changeset patch # User Christian Urban # Date 1412552778 -3600 # Node ID 332fbe9c91ab3a280ed1b0c44733aa89552c9f85 # Parent 4deef8ac5d72877b5b0851ba07f97f1e6da6362e added slides diff -r 4deef8ac5d72 -r 332fbe9c91ab graphics.sty --- a/graphics.sty Sun Oct 05 23:56:18 2014 +0100 +++ b/graphics.sty Mon Oct 06 00:46:18 2014 +0100 @@ -3,6 +3,9 @@ \usetikzlibrary{positioning} \usetikzlibrary{calc} \usetikzlibrary{automata} +\usetikzlibrary{arrows} +\usetikzlibrary{backgrounds} +\usetikzlibrary{fit} \usepackage{graphicx} \usepackage{pgfplots} diff -r 4deef8ac5d72 -r 332fbe9c91ab slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 4deef8ac5d72 -r 332fbe9c91ab slides/slides03.tex --- a/slides/slides03.tex Sun Oct 05 23:56:18 2014 +0100 +++ b/slides/slides03.tex Mon Oct 06 00:46:18 2014 +0100 @@ -1,41 +1,22 @@ \documentclass[dvipsnames,14pt,t]{beamer} -\usepackage{beamerthemeplaincu} -\usepackage[absolute,overlay]{textpos} -\usepackage{ifthen} -\usepackage{tikz} -\usepackage{pgf} -\usepackage{calc} -\usepackage{ulem} -\usepackage{courier} -\usepackage{listings} -\renewcommand{\uline}[1]{#1} -\usetikzlibrary{arrows} -\usetikzlibrary{automata} -\usetikzlibrary{shapes} -\usetikzlibrary{shadows} -\usetikzlibrary{positioning} -\usetikzlibrary{calc} -\usetikzlibrary{fit} -\usetikzlibrary{backgrounds} -\usepackage{graphicx} +\usepackage{../slides} +\usepackage{../graphics} \usepackage{../langs} \usepackage{../data} -\makeatletter -\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}} -\@empty\z@\@empty -\makeatother +\hfuzz=220pt + +\pgfplotsset{compat=1.11} + +\newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{AFL 03, King's College London, 9.~October 2013} -\newcommand{\bl}[1]{\textcolor{blue}{#1}} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions +\renewcommand{\slidecaption}{AFL 03, King's College London} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}<1>[t] +\begin{frame}[t] \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] @@ -43,12 +24,6 @@ \LARGE Formal Languages (3)\\[3mm] \end{tabular}} - %\begin{center} - %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} - %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ - %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} - %\end{center} - \normalsize \begin{center} \begin{tabular}{lp{8cm}} @@ -58,12 +33,10 @@ \end{tabular} \end{center} - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} @@ -77,35 +50,32 @@ \item comments \end{itemize}\bigskip - \mbox{}\hfill\bl{\url{http://www.regexper.com}} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Last Week\end{tabular}} +\frametitle{Last Week} Last week I showed you a regular expression matcher -which works provably correctly in all cases. +which works provably correct in all cases (we did not +do the proving part though) \begin{center} -\bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$} +\bl{$matches\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$} \end{center}\bigskip\bigskip \small \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} +\frametitle{The Derivative of a Rexp} \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} @@ -116,69 +86,62 @@ \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ - \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\ + \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\ - \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ - \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ + \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ + \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ \end{tabular} \end{center} - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] - To see what is going on, define \begin{center} \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } \end{center}\bigskip\bigskip -\small -For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then +For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then \begin{center} \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} -$Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\ -$Der\,b\,A$ & $=$ & $\{"ar"\}$\\ +$Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ +$Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ $Der\,a\,A$ & $=$ & $\varnothing$\\ \end{tabular}} \end{center} - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} +\frametitle{The Idea of the Algorithm} -If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$} +If we want to recognise the string \bl{$abc$} with regular expression \bl{$r$} then\medskip \begin{enumerate} \item \bl{$Der\,a\,(L(r))$}\pause \item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause -\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause +\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\bigskip\pause \item finally we test whether the empty string is in this set\pause\medskip \end{enumerate} -The matching algorithm works similarly, just over regular expression instead of sets. -\end{frame}} +The matching algorithm works similarly, just over regular expressions instead of sets. +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -Input: string \bl{$"abc"$} and regular expression \bl{$r$} +Input: string \bl{$abc$} and regular expression \bl{$r$} \begin{enumerate} \item \bl{$der\,a\,r$} @@ -187,31 +150,28 @@ \item finally check whether the last regular expression can match the empty string \end{enumerate} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] We proved already \begin{center} -\bl{$nullable(r)$} \;if and only if\; \bl{$"" \in L(r)$} +\bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$} \end{center} by induction on the regular expression.\bigskip\pause \begin{center} -\huge\bf \alert{Any Questions?} +{\huge\bf\alert{Any Questions?}} \end{center} - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] We need to prove @@ -221,14 +181,13 @@ \end{center} by induction on the regular expression. -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}} +\frametitle{Proofs about Rexps} \begin{itemize} \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip @@ -240,11 +199,10 @@ holds for \bl{$r$}. \end{itemize} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} @@ -255,20 +213,19 @@ \end{itemize}\bigskip \begin{itemize} -\item \bl{$P$} holds for \bl{$""$} and +\item \bl{$P$} holds for \bl{$[]$} and \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already holds for \bl{$s$} \end{itemize} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Languages\end{tabular}} +\frametitle{Languages} A \alert{language} is a set of strings.\bigskip @@ -277,14 +234,13 @@ A language is \alert{regular} iff there exists a regular expression that recognises all its strings.\bigskip\bigskip\pause -\textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$}.} -\end{frame}} +\textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$} is not} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[t] -\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} +\frametitle{Regular Expressions} \begin{center} \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} @@ -300,16 +256,15 @@ How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the set of languages we can recognise? -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}} +\frametitle{Negation of Regular Expr's} \begin{itemize} -\item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip +\item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip \item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$} @@ -321,45 +276,42 @@ \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} \] - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Negation\end{tabular}} +\frametitle{Negation} -Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only. -Find a regular expression that matches all strings \emph{except} \bl{ab} and \bl{ac}. +Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only. +Find a (basic!) regular expression that matches all strings \emph{\alert{except}} +\bl{$ab$} and \bl{$ac$}! -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} - -Lexing separates strings into ``words'' / components. - -\begin{itemize} -\item Identifiers (non-empty strings of letters or digits, starting with a letter) -\item Numbers (non-empty sequences of digits omitting leading zeros) -\item Keywords (else, if, while, \ldots) -\item White space (a non-empty sequence of blanks, newlines and tabs) -\item Comments -\end{itemize} - -\end{frame}} +%\mode{ +%\begin{frame}[c] +%\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} +% +%Lexing separates strings into ``words'' / components. +% +%\begin{itemize} +%\item Identifiers (non-empty strings of letters or digits, starting with a letter) +%\item Numbers (non-empty sequences of digits omitting leading zeros) +%\item Keywords (else, if, while, \ldots) +%\item White space (a non-empty sequence of blanks, newlines and tabs) +%\item Comments +%\end{itemize} +% +%\end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Automata\end{tabular}} +\frametitle{Automata} A \alert{deterministic finite automaton} consists of: @@ -370,7 +322,8 @@ \item there is transition function\medskip \small -which takes a state as argument and a character and produces a new state\smallskip\\ +which takes a state as argument and a character and produces a +new state\smallskip\\ this function might not be everywhere defined \end{itemize} @@ -378,12 +331,11 @@ \bl{$A(Q, q_0, F, \delta)$} \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \begin{center} @@ -413,11 +365,10 @@ \item all states might be accepting (but this does not necessarily mean all strings are accepted) \end{itemize} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \begin{center} @@ -449,15 +400,12 @@ \end{tabular}\ldots \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[t] -\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} +\frametitle{Accepting a String} Given @@ -469,7 +417,7 @@ \begin{center} \begin{tabular}{l} -\bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\ +\bl{$\hat{\delta}(q, []) \dn q$}\\ \bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\ \end{tabular} \end{center}\pause @@ -479,11 +427,10 @@ \begin{center} \hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$} \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} @@ -508,11 +455,10 @@ \end{tabular} \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \frametitle{Two NFA Examples} @@ -544,12 +490,10 @@ \end{tabular} \end{center} - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \frametitle{Rexp to NFA} @@ -572,11 +516,10 @@ \end{tabular} \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[t] \frametitle{Case $r_1\cdot r_2$} @@ -620,13 +563,13 @@ We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them via $\epsilon$-transitions to the starting state of the second automaton. -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[t] \frametitle{Case $r_1+ r_2$} +\mbox{}\\[-10mm] \onslide<1>{By recursion we are given two automata:\smallskip} @@ -666,7 +609,7 @@ \small We (1) need to introduce a new starting state and (2) connect it to the original two starting states. -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -754,6 +697,26 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Regexps and Automata} + +\begin{center} +\begin{tikzpicture} +\node (rexp) {\bl{\bf Regexps}}; +\node (nfa) [right=of rexp] {\bl{\bf NFAs}}; +\node (dfa) [right=of nfa] {\bl{\bf DFAs}}; +\onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};} +\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); +\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); +\onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);} +\onslide<2->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);} +\end{tikzpicture}\\ +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ @@ -772,48 +735,66 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}<2>[c] +\frametitle{DFA to Rexp} + +\begin{center} +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] + \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] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$b$}} () + ; +\end{tikzpicture} +\end{center} + +\onslide<3>{How to get from a DFA to a regular expression?} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ -\begin{frame}<1-2>[c] +\begin{frame}[c] \begin{center} -\begin{tikzpicture}[>=stealth',very thick,auto, - every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -\node[state,initial] (q_0) {$q_0$}; -\node[state] (q_1) [right=of q_0] {$q_1$}; -\node[state] (q_2) [below right=of q_0] {$q_2$}; -\node[state] (q_3) [right=of q_2] {$q_3$}; -\node[state, accepting] (q_4) [right=of q_1] {$q_4$}; -\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); -\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); -\path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); -\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); -\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); -\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); -\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); -\path[->] (q_2) edge [loop left] node {\alert{$b$}} (); -\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] + \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] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$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} - -\mbox{}\\[-20mm]\mbox{} - -\begin{center} -\begin{tikzpicture}[>=stealth',very thick,auto, - every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -\node[state,initial] (q_02) {$q_{0, 2}$}; -\node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; -\node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; -\path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); -\path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); -\path[->] (q_02) edge [loop below] node {\alert{$b$}} (); -\path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); -\path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); -\end{tikzpicture}\\ -minimal automaton -\end{center} +} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -822,6 +803,49 @@ \mode{ \begin{frame}[c] +\begin{center} +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] + \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] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$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] + Given the function \begin{center} diff -r 4deef8ac5d72 -r 332fbe9c91ab slides/slides04.tex --- a/slides/slides04.tex Sun Oct 05 23:56:18 2014 +0100 +++ b/slides/slides04.tex Mon Oct 06 00:46:18 2014 +0100 @@ -646,6 +646,50 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}<1-2>[c] + +\begin{center} +\begin{tikzpicture}[>=stealth',very thick,auto, + every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] +\node[state,initial] (q_0) {$q_0$}; +\node[state] (q_1) [right=of q_0] {$q_1$}; +\node[state] (q_2) [below right=of q_0] {$q_2$}; +\node[state] (q_3) [right=of q_2] {$q_3$}; +\node[state, accepting] (q_4) [right=of q_1] {$q_4$}; +\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); +\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); +\path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); +\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); +\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); +\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); +\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); +\path[->] (q_2) edge [loop left] node {\alert{$b$}} (); +\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); +\end{tikzpicture} +\end{center} + +\mbox{}\\[-20mm]\mbox{} + +\begin{center} +\begin{tikzpicture}[>=stealth',very thick,auto, + every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] +\node[state,initial] (q_02) {$q_{0, 2}$}; +\node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; +\node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; +\path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); +\path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); +\path[->] (q_02) edge [loop below] node {\alert{$b$}} (); +\path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); +\path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); +\end{tikzpicture}\\ +minimal automaton +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{