# HG changeset patch # User Christian Urban # Date 1381885622 -3600 # Node ID 920f675b4ed172c3a5506a4f4c7bde81740edc2f # Parent 0cb61bed557da572de31e6612ac7586e11551a7d added diff -r 0cb61bed557d -r 920f675b4ed1 progs/dfa.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/dfa.scala Wed Oct 16 02:07:02 2013 +0100 @@ -0,0 +1,64 @@ +// DFAs +import scala.util._ + +abstract class State +type States = Set[State] + +case class IntState(i: Int) extends State + +object NewState { + var counter = 0 + + def apply() : IntState = { + counter += 1; + new IntState(counter - 1) + } +} + + +// DFA class +case class DFA(states: States, + start: State, + delta: (State, Char) => State, + fins: States) { + + def deltas(q: State, s: List[Char]) : State = s match { + case Nil => q + case c::cs => deltas(delta(q, c), cs) + } + + // wether a string is accepted by the automaton or not + def accepts(s: String) : Boolean = + Try(fins contains + (deltas(start, s.toList))) getOrElse false +} + + +// example DFA from the lectures +val Q0 = NewState() +val Q1 = NewState() +val Q2 = NewState() +val Q3 = NewState() +val Q4 = NewState() + + +val delta : (State, Char) => State = { + case (Q0, 'a') => Q1 + case (Q0, 'b') => Q2 + case (Q1, 'a') => Q4 + case (Q1, 'b') => Q2 + case (Q2, 'a') => Q3 + case (Q2, 'b') => Q2 + case (Q3, 'a') => Q4 + case (Q3, 'b') => Q0 + case (Q4, 'a') => Q4 + case (Q4, 'b') => Q4 +} + +val DFA1 = DFA(Set(Q0, Q1, Q2, Q3, Q4), Q0, delta, Set(Q4)) + +println(DFA1.accepts("aaa")) +println(DFA1.accepts("bb")) +println(DFA1.accepts("aaac")) + + diff -r 0cb61bed557d -r 920f675b4ed1 progs/nfa.scala --- a/progs/nfa.scala Tue Oct 15 22:14:04 2013 +0100 +++ b/progs/nfa.scala Wed Oct 16 02:07:02 2013 +0100 @@ -212,7 +212,7 @@ def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) // test harness for the matcher -for (i <- 1 to 100) { +for (i <- 0 to 100 by 5) { println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) } @@ -233,7 +233,7 @@ def matcher2(r: Rexp, s: String) : Boolean = accepts2(thompson(r), s) // test harness for the backtracking matcher -for (i <- 1 to 21) { +for (i <- 0 to 20 by 1) { println(i + ": " + "%.5f".format(time_needed(1, matcher2(EVIL(i), "a" * i)))) } diff -r 0cb61bed557d -r 920f675b4ed1 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 0cb61bed557d -r 920f675b4ed1 slides/slides04.tex --- a/slides/slides04.tex Tue Oct 15 22:14:04 2013 +0100 +++ b/slides/slides04.tex Wed Oct 16 02:07:02 2013 +0100 @@ -18,6 +18,9 @@ \usetikzlibrary{shadows} \usetikzlibrary{positioning} \usetikzlibrary{calc} +\usetikzlibrary{fit} +\usetikzlibrary{plotmarks} +\usetikzlibrary{backgrounds} \usepackage{graphicx} \definecolor{javared}{rgb}{0.6,0,0} % for strings @@ -25,8 +28,13 @@ \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc +\makeatletter +\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}} +\@empty\z@\@empty +\makeatother + \lstset{language=Java, - basicstyle=\ttfamily, + basicstyle=\consolas, keywordstyle=\color{javapurple}\bfseries, stringstyle=\color{javagreen}, commentstyle=\color{javagreen}, @@ -47,7 +55,7 @@ private,protected,requires,return,sealed,% super,this,throw,trait,true,try,% type,val,var,while,with,yield}, - otherkeywords={=>,<-,<\%,<:,>:,\#,@}, + otherkeywords={=>,<-,<\%,<:,>:,\#,@,->}, sensitive=true, morecomment=[l]{//}, morecomment=[n]{/*}{*/}, @@ -57,7 +65,7 @@ } \lstset{language=Scala, - basicstyle=\ttfamily, + basicstyle=\consolas, keywordstyle=\color{javapurple}\bfseries, stringstyle=\color{javagreen}, commentstyle=\color{javagreen}, @@ -69,12 +77,113 @@ tabsize=2, showspaces=false, showstringspaces=false} - + % beamer stuff \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 +% The data files, written on the first run. +\begin{filecontents}{re-python.data} +1 0.029 +5 0.029 +10 0.029 +15 0.032 +16 0.042 +17 0.042 +18 0.055 +19 0.084 +20 0.136 +21 0.248 +22 0.464 +23 0.899 +24 1.773 +25 3.505 +26 6.993 +27 14.503 +28 29.307 +#29 58.886 +\end{filecontents} + +\begin{filecontents}{re-ruby.data} +1 0.00006 +2 0.00003 +3 0.00001 +4 0.00001 +5 0.00001 +6 0.00002 +7 0.00002 +8 0.00004 +9 0.00007 +10 0.00013 +11 0.00026 +12 0.00055 +13 0.00106 +14 0.00196 +15 0.00378 +16 0.00764 +17 0.01606 +18 0.03094 +19 0.06508 +20 0.12420 +21 0.25393 +22 0.51449 +23 1.02174 +24 2.05998 +25 4.22514 +26 8.42479 +27 16.88678 +28 34.79653 +\end{filecontents} + +\begin{filecontents}{nfa.data} +0 0.00099 +5 0.01304 +10 0.05350 +15 0.10152 +20 0.10876 +25 0.06984 +30 0.09693 +35 0.04805 +40 0.07512 +45 0.07624 +50 0.10451 +55 0.13285 +60 0.15748 +65 0.19982 +70 0.24075 +75 0.28963 +80 0.35734 +85 0.43735 +90 0.49692 +95 0.59551 +100 0.72236 +\end{filecontents} + +\begin{filecontents}{nfasearch.data} +0 0.00009 +1 0.00147 +2 0.00030 +3 0.00062 +4 0.00132 +5 0.00177 +6 0.00487 +7 0.00947 +8 0.01757 +9 0.02050 +10 0.02091 +11 0.04002 +12 0.08662 +13 0.17269 +14 0.37255 +15 0.81935 +16 1.76254 +17 3.89442 +18 8.42263 +19 17.89661 +20 38.21481 +\end{filecontents} + \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -122,6 +231,572 @@ \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}} + +\mbox{}\\[-13mm] + +\begin{tikzpicture}[y=.2cm, x=.09cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (100,0); + \draw (0,0) -- coordinate (y axis mid) (0,30); + %ticks + \foreach \x in {0,10,...,100} + \draw (\x,1pt) -- (\x,-3pt) + node[anchor=north] {\x}; + \foreach \y in {0,5,...,30} + \draw (1pt,\y) -- (-3pt,\y) + node[anchor=east] {\y}; + %labels + \node[below=0.6cm] at (x axis mid) {\bl{a}s}; + \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; + + %plots + \draw[color=blue] plot[mark=*, mark options={fill=white}] + file {re-python.data}; + \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] + file {nfa.data}; + \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] + file {re-ruby.data}; + + + %legend + \begin{scope}[shift={(4,20)}] + \draw[color=blue] (0,0) -- + plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Python}; + \draw[yshift=-\baselineskip, color=brown] (0,0) -- + plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Ruby}; + \draw[yshift=\baselineskip, color=red] (0,0) -- + plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small NFA 1}; + \end{scope} +\end{tikzpicture} + +\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{ +\begin{frame}[t] +\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} + +\mbox{}\\[-13mm] + +\begin{tikzpicture}[y=.2cm, x=.3cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (30,0); + \draw (0,0) -- coordinate (y axis mid) (0,30); + %ticks + \foreach \x in {0,5,...,30} + \draw (\x,1pt) -- (\x,-3pt) + node[anchor=north] {\x}; + \foreach \y in {0,5,...,30} + \draw (1pt,\y) -- (-3pt,\y) + node[anchor=east] {\y}; + %labels + \node[below=0.6cm] at (x axis mid) {\bl{a}s}; + \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; + + %plots + \draw[color=blue] plot[mark=*, mark options={fill=white}] + file {re-python.data}; + \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] + file {nfasearch.data}; + \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] + file {re-ruby.data}; + + %legend + \begin{scope}[shift={(4,20)}] + \draw[color=blue] (0,0) -- + plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Python}; + \draw[yshift=-\baselineskip, color=brown] (0,0) -- + plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Ruby}; + \draw[yshift=\baselineskip, color=red] (0,0) -- + plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small NFA 2}; + \end{scope} +\end{tikzpicture} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}<2>[c] +\frametitle{DFA to Rexp} + +\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} +\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{DFA Minimisation} + +\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 no chance. +\item All unmarked pairs can be merged. +\end{enumerate} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -146,7 +821,7 @@ \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} +\end{center}\pause \mbox{}\\[-20mm]\mbox{} @@ -168,532 +843,19 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{enumerate} -\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} -\item Mark all pairs that are 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 no chance. -\item All unmarked pairs can be merged. -\end{enumerate} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Last Week\end{tabular}} - -Last week I showed you\bigskip - -\begin{itemize} -\item a tokenizer taking a list of regular expressions\bigskip - -\item tokenization identifies lexeme in an input stream of characters (or string) -and cathegorizes them into tokens - -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Two Rules\end{tabular}} - -\begin{itemize} -\item Longest match rule (maximal munch rule): The -longest initial substring matched by any regular expression is taken -as next token.\bigskip - -\item Rule priority: -For a particular longest initial substring, the first regular -expression that can match determines the token. - -\end{itemize} - -%\url{http://www.technologyreview.com/tr10/?year=2011} - -%finite deterministic automata/ nondeterministic automaton - -%\item problem with infix operations, for example i-12 - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\mode{ -\begin{frame}[t] - -\begin{center} -\texttt{"if true then then 42 else +"} -\end{center} - - -\begin{tabular}{@{}l} -KEYWORD: \\ -\hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\ -WHITESPACE:\\ -\hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\ -IDENT:\\ -\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\ -NUM:\\ -\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ -OP:\\ -\hspace{5mm}\texttt{"+"}\\ -COMMENT:\\ -\hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"} -\end{tabular} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] - -\begin{center} -\texttt{"if true then then 42 else +"} -\end{center} - -\only<1>{ -\small\begin{tabular}{l} -KEYWORD(if),\\ -WHITESPACE,\\ -IDENT(true),\\ -WHITESPACE,\\ -KEYWORD(then),\\ -WHITESPACE,\\ -KEYWORD(then),\\ -WHITESPACE,\\ -NUM(42),\\ -WHITESPACE,\\ -KEYWORD(else),\\ -WHITESPACE,\\ -OP(+) -\end{tabular}} - -\only<2>{ -\small\begin{tabular}{l} -KEYWORD(if),\\ -IDENT(true),\\ -KEYWORD(then),\\ -KEYWORD(then),\\ -NUM(42),\\ -KEYWORD(else),\\ -OP(+) -\end{tabular}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - - -There is one small problem with the tokenizer. How should we -tokenize: - -\begin{center} -\texttt{"x - 3"} -\end{center} - -\begin{tabular}{@{}l} -OP:\\ -\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\ -NUM:\\ -\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ -NUMBER:\\ -\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\ -\end{tabular} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Negation\end{tabular}} - -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}, \bl{ac} and \bl{cba}. - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}} - -A deterministic finite automaton consists of: - -\begin{itemize} -\item a finite set of states -\item one of these states is the start state -\item some states are accepting states, and -\item there is transition function\medskip - -\small -which takes a state and a character as arguments and produces a new state\smallskip\\ -this function might not always be defined everywhere -\end{itemize} - -\begin{center} -\bl{$A(Q, q_0, F, \delta)$} -\end{center} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\includegraphics[scale=0.7]{pics/ch3.jpg} -\end{center}\pause - -\begin{itemize} -\item start can be an accepting state -\item it is possible that there is no accepting state -\item all states might be accepting (but does not necessarily mean all strings are accepted) -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\includegraphics[scale=0.7]{pics/ch3.jpg} -\end{center} - -for this automaton \bl{$\delta$} is the function\\ - -\begin{center} -\begin{tabular}{lll} -\bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\ -\bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\ -\end{tabular}\ldots -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} - -Given - -\begin{center} -\bl{$A(Q, q_0, F, \delta)$} -\end{center} - -you can define - -\begin{center} -\begin{tabular}{l} -\bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ -\bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\ -\end{tabular} -\end{center}\pause - -Whether a string \bl{$s$} is accepted by \bl{$A$}? - -\begin{center} -\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$} -\end{center} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} - -A non-deterministic finite automaton consists again of: - -\begin{itemize} -\item a finite set of states -\item one of these states is the start state -\item some states are accepting states, and -\item there is transition \alert{relation}\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] - -\begin{center} -\includegraphics[scale=0.7]{pics/ch5.jpg} -\end{center} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\begin{tabular}[b]{ll} -\bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\ -\bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\ -\bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\ -\end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\begin{tabular}[t]{ll} -\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\ -\end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\begin{tabular}[t]{ll} -\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\ -\end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\begin{tabular}[b]{ll} -\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\ -\end{tabular} -\end{center}\pause\bigskip - -Why can't we just have an epsilon transition from the accepting states to the starting state? - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}} - - -\begin{textblock}{5}(1,2.5) -\includegraphics[scale=0.5]{pics/ch5.jpg} -\end{textblock} - -\begin{textblock}{11}(6.5,4.5) -\begin{tabular}{r|cl} -& a & b\\ -\hline -$\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\ -$\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\ -$\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\ -$\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\ -$\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\ -$\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ -$\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\ -\onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ -\end{tabular} -\end{textblock} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} - -A language is \alert{regular} iff there exists -a regular expression that recognises all its strings.\bigskip\medskip - -or equivalently\bigskip\medskip - -A language is \alert{regular} iff there exists -a deterministic finite automaton that recognises all its strings.\bigskip\pause - -Why is every finite set of strings a regular language? -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\includegraphics[scale=0.5]{pics/ch3.jpg} -\end{center} - -\begin{center} -\includegraphics[scale=0.5]{pics/ch4.jpg}\\ -minimal automaton -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\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 no chance. -\item All unmarked pairs can be merged. -\end{enumerate} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -Given the function - -\begin{center} -\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} -$rev(\varnothing)$ & $\dn$ & $\varnothing$\\ -$rev(\epsilon)$ & $\dn$ & $\epsilon$\\ -$rev(c)$ & $\dn$ & $c$\\ -$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ -$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ -$rev(r^*)$ & $\dn$ & $rev(r)^*$\\ -\end{tabular}} -\end{center} - - -and the set - -\begin{center} -\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$} -\end{center} - -prove whether - -\begin{center} -\bl{$L(rev(r)) = Rev (L(r))$} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] \begin{itemize} -\item The star-case in our proof about the matcher needs the following lemma -\begin{center} -\bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$} -\end{center} -\end{itemize}\bigskip\bigskip - -\begin{itemize} -\item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip -\item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B} - +\item Assuming you have the alphabet \bl{$\{a, b, c\}$}\bigskip +\item Give a regular expression that can recognise all strings that have at least one \bl{$b$}. \end{itemize} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{itemize} -\item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip -\item Give a regular expression that can recognise all strings that have at least one \bl{b}. -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -``I hate coding. I do not want to look at code.'' - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - \end{document} %%% Local Variables: