# HG changeset patch # User Christian Urban # Date 1413031836 -3600 # Node ID 4dbeaf43031d71ac78214c7f7c49334ba7177575 # Parent 83e6cb90216d0e0b222f3133c8f59a37a9925753 updated diff -r 83e6cb90216d -r 4dbeaf43031d handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 83e6cb90216d -r 4dbeaf43031d handouts/ho03.tex --- a/handouts/ho03.tex Sat Oct 11 13:09:15 2014 +0100 +++ b/handouts/ho03.tex Sat Oct 11 13:50:36 2014 +0100 @@ -464,6 +464,151 @@ \subsubsection*{Automata Minimization} +As seen in the subset construction, the translation +of an NFA to a DFA can result in a rather ``inefficient'' +DFA. Meaning there are states that are not needed. A +DFA can be \emph{minimised} by the following algorithm: + +\begin{enumerate} +\item Take all pairs $(q, p)$ with $q \not= p$ +\item Mark all pairs that accepting and non-accepting states +\item For all unmarked pairs $(q, p)$ and all characters $c$ + test whether + + \begin{center} + $(\delta(q, c), \delta(p,c))$ + \end{center} + + are marked. If there is one, then also mark $(q, p)$. +\item Repeat last step until no change. +\item All unmarked pairs can be merged. +\end{enumerate} + +\noindent To illustrate this algorithm, consider the following +DFA. + +\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] {$a$} (q_1); +\path[->] (q_1) edge node [above] {$a$} (q_4); +\path[->] (q_4) edge [loop right] node {$a, b$} (); +\path[->] (q_3) edge node [right] {$a$} (q_4); +\path[->] (q_2) edge node [above] {$a$} (q_3); +\path[->] (q_1) edge node [right] {$b$} (q_2); +\path[->] (q_0) edge node [above] {$b$} (q_2); +\path[->] (q_2) edge [loop left] node {$b$} (); +\path[->] (q_3) edge [bend left=95, looseness=1.3] node + [below] {$b$} (q_0); +\end{tikzpicture} +\end{center} + +\noindent In Step 1 and 2 we consider essentially a triangle +of the form + +\begin{center} +\begin{tikzpicture}[scale=0.6,line width=0.8mm] +\draw (0,0) -- (4,0); +\draw (0,1) -- (4,1); +\draw (0,2) -- (3,2); +\draw (0,3) -- (2,3); +\draw (0,4) -- (1,4); + +\draw (0,0) -- (0, 4); +\draw (1,0) -- (1, 4); +\draw (2,0) -- (2, 3); +\draw (3,0) -- (3, 2); +\draw (4,0) -- (4, 1); + +\draw (0.5,-0.5) node {$q_0$}; +\draw (1.5,-0.5) node {$q_1$}; +\draw (2.5,-0.5) node {$q_2$}; +\draw (3.5,-0.5) node {$q_3$}; + +\draw (-0.5, 3.5) node {$q_1$}; +\draw (-0.5, 2.5) node {$q_2$}; +\draw (-0.5, 1.5) node {$q_3$}; +\draw (-0.5, 0.5) node {$q_4$}; + +\draw (0.5,0.5) node {\large$\star$}; +\draw (1.5,0.5) node {\large$\star$}; +\draw (2.5,0.5) node {\large$\star$}; +\draw (3.5,0.5) node {\large$\star$}; +\end{tikzpicture} +\end{center} + +\noindent where the lower row is filled with stars, because in +the corresponding pairs there is always one state that is +accepting ($q_4$) and a state that is non-accepting (the other +states). + +Now in Step 3 we need to fill in more stars according whether +one of the next-state pairs are marked. We have to do this +for every unmarked field until there is no change anymore. +This gives the triangle + +\begin{center} +\begin{tikzpicture}[scale=0.6,line width=0.8mm] +\draw (0,0) -- (4,0); +\draw (0,1) -- (4,1); +\draw (0,2) -- (3,2); +\draw (0,3) -- (2,3); +\draw (0,4) -- (1,4); + +\draw (0,0) -- (0, 4); +\draw (1,0) -- (1, 4); +\draw (2,0) -- (2, 3); +\draw (3,0) -- (3, 2); +\draw (4,0) -- (4, 1); + +\draw (0.5,-0.5) node {$q_0$}; +\draw (1.5,-0.5) node {$q_1$}; +\draw (2.5,-0.5) node {$q_2$}; +\draw (3.5,-0.5) node {$q_3$}; + +\draw (-0.5, 3.5) node {$q_1$}; +\draw (-0.5, 2.5) node {$q_2$}; +\draw (-0.5, 1.5) node {$q_3$}; +\draw (-0.5, 0.5) node {$q_4$}; + +\draw (0.5,0.5) node {\large$\star$}; +\draw (1.5,0.5) node {\large$\star$}; +\draw (2.5,0.5) node {\large$\star$}; +\draw (3.5,0.5) node {\large$\star$}; +\draw (0.5,1.5) node {\large$\star$}; +\draw (2.5,1.5) node {\large$\star$}; +\draw (0.5,3.5) node {\large$\star$}; +\draw (1.5,2.5) node {\large$\star$}; +\end{tikzpicture} +\end{center} + +\noindent which means states $q_0$ and $q_2$, as well as $q_1$ +and $q_3$ can be merged. This gives the following minimal DFA + +\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] {$a$} (q_13); +\path[->] (q_13) edge [bend left] node [below] {$b$} (q_02); +\path[->] (q_02) edge [loop below] node {$b$} (); +\path[->] (q_13) edge node [above] {$a$} (q_4); +\path[->] (q_4) edge [loop above] node {$a, b$} (); +\end{tikzpicture} +\end{center} + \subsubsection*{Regular Languages} Given the constructions in the previous sections we obtain @@ -549,6 +694,9 @@ the accepting and non-accepting states. You can then translate this DFA back into a regular expression. +Not all languages are regular\ldots{} + + \end{document} %%% Local Variables: diff -r 83e6cb90216d -r 4dbeaf43031d slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 83e6cb90216d -r 4dbeaf43031d slides/slides04.tex --- a/slides/slides04.tex Sat Oct 11 13:09:15 2014 +0100 +++ b/slides/slides04.tex Sat Oct 11 13:50:36 2014 +0100 @@ -1,42 +1,21 @@ \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{plotmarks} -\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}} -\renewcommand{\slidecaption}{AFL 04, King's College London, 16.~October 2013} -\newcommand{\bl}[1]{\textcolor{blue}{#1}} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions +\renewcommand{\slidecaption}{AFL 04, King's College London} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}<1>[t] +\begin{frame}[t] \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] @@ -52,9 +31,7 @@ Slides: & KEATS (also home work is there)\\ \end{tabular} \end{center} - - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -79,348 +56,10 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}DFAs\end{tabular}} - -A deterministic finite automaton consists of: - -\begin{itemize} -\item a finite set of states, \bl{$Q$} -\item one of these states is the start state, \bl{$q_0$} -\item there is transition function, \bl{$\delta$}, and -\item some states are accepting states, \bl{$F$} -\medskip -\end{itemize} - -\begin{center} -\bl{$A(Q, q_0, \delta, F)$} -\end{center} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}State Nodes\end{tabular}} - -\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont -\lstinputlisting{../progs/appA.scala}}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}DFAs\;\;\;\end{tabular}} - -\mbox{}\\[7mm] - -\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont -\lstinputlisting{../progs/appB.scala}}} - -\only<2->{ -\begin{textblock}{9}(7.5,0.5) -\begin{tikzpicture} -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\normalsize\color{darkgray} -\begin{minipage}{6cm} -\begin{tabular}{l} -\bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\ -\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\[4mm] -\bl{$\hat{\delta}(q_0, s) \in F$} -\end{tabular} -\end{minipage}}; -\end{tikzpicture} -\end{textblock}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] - -\mbox{}\hspace{-10mm} -\begin{tikzpicture}[scale=0.6,>=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} - -\only<1->{ -\begin{textblock}{9}(7.4,3.5) -\begin{tikzpicture} -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\normalsize\color{darkgray} -\begin{minipage}{6.6cm} -\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont -\lstinputlisting{../progs/appC.scala}}} -\end{minipage}}; -\end{tikzpicture} -\end{textblock}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}NFAs\end{tabular}} - -A non-deterministic finite automaton \bl{$A(Q, q_0, \delta, F)$} consists of:\medskip - -\begin{itemize} -\item a finite set of states, \bl{$Q$} -\item one of these states is the start state, \bl{$q_0$} -\item some states are accepting states, \bl{$F$}, -\item there is transition \alert{relation}, \bl{$\delta$}, and -\item there are \alert{silent} transitions\medskip -\end{itemize} - - -\begin{center} -\begin{tabular}{c} -\bl{$(q_1, a) \rightarrow q_2$}\\ -\bl{$(q_1, a) \rightarrow q_3$}\\ -\end{tabular} -\hspace{10mm} -\begin{tabular}{c} -\bl{$(q_1, \epsilon) \rightarrow q_2$}\\ -\end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont -\lstinputlisting{../progs/appD.scala}}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[t] - -\mbox{}\hspace{-10mm} -\begin{tikzpicture}[scale=0.6,>=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) [above=of q_0] {$q_1$}; -\node[state, accepting] (q_2) [below=of q_0] {$q_2$}; -\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1); -\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2); -\path[->] (q_0) edge [loop right] node {\alert{$a$}} (); -\path[->] (q_1) edge [loop above] node {\alert{$a$}} (); -\path[->] (q_2) edge [loop below] node {\alert{$b$}} (); -\end{tikzpicture} - -\only<1->{ -\begin{textblock}{9}(6,1.5) -\begin{tikzpicture} -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\normalsize\color{darkgray} -\begin{minipage}{7cm} -\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont -\lstinputlisting{../progs/appE.scala}}} -\end{minipage}}; -\end{tikzpicture} -\end{textblock}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Rexp to NFA} - -Thompson's construction of a NFA from a regular expression: - -\begin{center} -\begin{tabular}[t]{l@{\hspace{10mm}}l} -\raisebox{1mm}{\bl{$\varnothing$}} & -\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] -\node[state, initial] (q_0) {$\mbox{}$}; -\end{tikzpicture}\\\\ -\raisebox{1mm}{\bl{$\epsilon$}} & -\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] -\node[state, initial, accepting] (q_0) {$\mbox{}$}; -\end{tikzpicture}\\\\ -\raisebox{2mm}{\bl{$c$}} & -\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] -\node[state, initial] (q_0) {$\mbox{}$}; -\node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$}; -\path[->] (q_0) edge node [below] {\alert{$c$}} (q_1); -\end{tikzpicture}\\\\ -\end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{Case $r_1\cdot r_2$} - -\mbox{}\bigskip -\onslide<1>{By recursion we are given two automata:\bigskip} - -{\centering\begin{tikzpicture}[node distance=3mm, - >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] -\node[state, initial] (q_0) {$\mbox{}$}; -\node (r_1) [right=of q_0] {$\ldots$}; -\only<1>{ -\node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$}; -\node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$}; -\node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$};} -\only<2>{ -\node[state] (t_1) [right=of r_1] {$\mbox{}$}; -\node[state] (t_2) [above=of t_1] {$\mbox{}$}; -\node[state] (t_3) [below=of t_1] {$\mbox{}$};} -\only<1>{\node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$};} -\only<2>{\node[state] (a_0) [right=2.5cm of t_1] {$\mbox{}$};} -\node (b_1) [right=of a_0] {$\ldots$}; -\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$}; -\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$}; -\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$}; -\only<2>{ -\path[->] (t_1) edge node [above, pos=0.3] {\alert{$\epsilon$}} (a_0); -\path[->] (t_2) edge node [above] {\alert{$\epsilon$}} (a_0); -\path[->] (t_3) edge node [below] {\alert{$\epsilon$}} (a_0); -} -\begin{pgfonlayer}{background} -\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};} -\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};} -\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};} -\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};} -\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};} -\only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};} -\end{pgfonlayer} -\end{tikzpicture}}\bigskip\bigskip - -\small -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}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{Case $r_1+ r_2$} - -\onslide<1>{By recursion we are given two automata:\smallskip} - -\hspace{2cm}\begin{tikzpicture}[node distance=3mm, - >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] -\onslide<1>{\node at (0,0) (1) {$\mbox{}$};} -\onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};} -\only<1>{ -\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$}; -\node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};} -\only<2>{ -\node[state] (2) [above right=16mm of 1] {$\mbox{}$}; -\node[state] (3) [below right=16mm of 1] {$\mbox{}$};} - -\node (a) [right=of 2] {$\ldots$}; -\node[state, accepting] (a1) [right=of a] {$\mbox{}$}; -\node[state, accepting] (a2) [above=of a1] {$\mbox{}$}; -\node[state, accepting] (a3) [below=of a1] {$\mbox{}$}; - -\node (b) [right=of 3] {$\ldots$}; -\node[state, accepting] (b1) [right=of b] {$\mbox{}$}; -\node[state, accepting] (b2) [above=of b1] {$\mbox{}$}; -\node[state, accepting] (b3) [below=of b1] {$\mbox{}$}; -\only<2>{ -\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2); -\path[->] (1) edge node [below] {\alert{$\epsilon$}} (3); -} -\begin{pgfonlayer}{background} -\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};} -\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};} -\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};} -\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};} -\only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};} -\only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};} -\end{pgfonlayer} -\end{tikzpicture} - -\small -We (1) need to introduce a new starting state and (2) connect it to the original two starting states. -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Case $r^*$} - -\onslide<1>{By recursion we are given an automaton for $r$:\smallskip} - -\hspace{2cm}\begin{tikzpicture}[node distance=3mm, - >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] -\onslide<1>{\node at (0,0) (1) {$\mbox{}$};} -\onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};} -\only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};} -\only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};} -\node (a) [right=of 2] {$\ldots$}; -\only<1>{ -\node[state, accepting] (a1) [right=of a] {$\mbox{}$}; -\node[state, accepting] (a2) [above=of a1] {$\mbox{}$}; -\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};} -\only<2->{ -\node[state] (a1) [right=of a] {$\mbox{}$}; -\node[state] (a2) [above=of a1] {$\mbox{}$}; -\node[state] (a3) [below=of a1] {$\mbox{}$};} -\only<2->{ -\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2); -\path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1); -\path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1); -\path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1); - -} -\begin{pgfonlayer}{background} -\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};} -\only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};} -\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};} -\only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};} -\end{pgfonlayer} -\end{tikzpicture}\bigskip - -\onslide<3->{ -Why can't we just have an epsilon transition from the accepting states to the starting state?} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} +\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} \mbox{}\\[-13mm] @@ -462,19 +101,9 @@ \end{scope} \end{tikzpicture} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Greedy Depth-First} - -\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont -\lstinputlisting{../progs/appG.scala}}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ @@ -634,12 +263,12 @@ \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 +\item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether \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 no chance. +\item Repeat last step until no change. \item All unmarked pairs can be merged. \end{enumerate} @@ -647,8 +276,67 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\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); +\end{tikzpicture} +\end{center} + +\mbox{}\\[-20mm]\mbox{} + +\begin{center} +\begin{tikzpicture}[scale=0.8,line width=0.8mm] +\draw (0,0) -- (4,0); +\draw (0,1) -- (4,1); +\draw (0,2) -- (3,2); +\draw (0,3) -- (2,3); +\draw (0,4) -- (1,4); + +\draw (0,0) -- (0, 4); +\draw (1,0) -- (1, 4); +\draw (2,0) -- (2, 3); +\draw (3,0) -- (3, 2); +\draw (4,0) -- (4, 1); + +\draw (0.5,-0.5) node {$q_0$}; +\draw (1.5,-0.5) node {$q_1$}; +\draw (2.5,-0.5) node {$q_2$}; +\draw (3.5,-0.5) node {$q_3$}; + +\draw (-0.5, 3.5) node {$q_1$}; +\draw (-0.5, 2.5) node {$q_2$}; +\draw (-0.5, 1.5) node {$q_3$}; +\draw (-0.5, 0.5) node {$q_4$}; + +\draw (0.5,0.5) node {\large$\star$}; +\draw (1.5,0.5) node {\large$\star$}; +\draw (2.5,0.5) node {\large$\star$}; +\draw (3.5,0.5) node {\large$\star$}; +\end{tikzpicture} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] \begin{center} \begin{tikzpicture}[>=stealth',very thick,auto, @@ -687,7 +375,7 @@ minimal automaton \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff -r 83e6cb90216d -r 4dbeaf43031d slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 83e6cb90216d -r 4dbeaf43031d slides/slides05.tex --- a/slides/slides05.tex Sat Oct 11 13:09:15 2014 +0100 +++ b/slides/slides05.tex Sat Oct 11 13:50:36 2014 +0100 @@ -1,37 +1,23 @@ \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} -\usepackage{graphicx} -\usepackage{pgfplots} -\usepackage{fontspec} +\usepackage{../slides} +\usepackage{../graphics} \usepackage{../langs} \usepackage{../data} +\hfuzz=220pt + +\pgfplotsset{compat=1.11} + +\newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{AFL 05, King's College London, 23.~October 2013} -\newcommand{\bl}[1]{\textcolor{blue}{#1}} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions +\renewcommand{\slidecaption}{AFL 05, King's College London} + \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}<1>[t] +\begin{frame}[t] \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] @@ -47,9 +33,7 @@ Slides: & KEATS (also home work is there)\\ \end{tabular} \end{center} - - -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -65,7 +49,7 @@ \bl{$(\delta(q, c), \delta(p,c))$} \end{center} are marked. If yes, then also mark \bl{$(q, p)$}. -\item Repeat last step until no chance. +\item Repeat last step until no change. \item All unmarked pairs can be merged. \end{enumerate} @@ -75,7 +59,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ -\begin{frame}<1-2>[c] +\begin{frame}<1>[c] \begin{center} \begin{tikzpicture}[>=stealth',very thick,auto,