\documentclass{article}\usepackage{../style}\usepackage{../langs}\usepackage{../graphics}\begin{document}\section*{Handout 3 (Automata)}Every formal language course I know of bombards you first withautomata and then to a much, much smaller extend with regularexpressions. As you can see, this course is turned upsidedown: regular expressions come first. The reason is thatregular expressions are easier to reason about and the notionof derivatives, although already quite old, only became morewidely known rather recently. Still let us in this lecturehave a closer look at automata and their relation to regularexpressions. This will help us with understanding why theregular expression matchers in Python and Ruby are so slowwith certain regular expressions. The central definitionis:\medskip \noindent A \emph{deterministic finite automaton} (DFA), say $A$, isdefined by a four-tuple written $A(Q, q_0, F, \delta)$ where\begin{itemize}\item $Q$ is a finite set of states,\item $q_0 \in Q$ is the start state,\item $F \subseteq Q$ are the accepting states, and\item $\delta$ is the transition function.\end{itemize}\noindent The transition function determines how to``transition'' from one state to the next state with respectto a character. We have the assumption that these transitionfunctions do not need to be defined everywhere: so it can bethe case that given a character there is no next state, inwhich case we need to raise a kind of ``failure exception''. Atypical example of a DFA is\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},scale=2]\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 this graphical notation, the accepting state$q_4$ is indicated with double circles. Note that there can bemore than one accepting state. It is also possible that a DFAhas no accepting states at all, or that the starting state isalso an accepting state. In the case above the transitionfunction is defined everywhere and can be given as a table asfollows:\[\begin{array}{lcl}(q_0, a) &\rightarrow& q_1\\(q_0, b) &\rightarrow& q_2\\(q_1, a) &\rightarrow& q_4\\(q_1, b) &\rightarrow& q_2\\(q_2, a) &\rightarrow& q_3\\(q_2, b) &\rightarrow& q_2\\(q_3, a) &\rightarrow& q_4\\(q_3, b) &\rightarrow& q_0\\(q_4, a) &\rightarrow& q_4\\(q_4, b) &\rightarrow& q_4\\\end{array}\]We need to define the notion of what language is accepted byan automaton. For this we lift the transition function$\delta$ from characters to strings as follows:\[\begin{array}{lcl}\hat{\delta}(q, []) & \dn & q\\\hat{\delta}(q, c\!::\!s) & \dn & \hat{\delta}(\delta(q, c), s)\\\end{array}\]\noindent This lifted transition function is often called``delta-hat''. Given a string, we start in the starting stateand take the first character of the string, follow to the nextsate, then take the second character and so on. Once thestring is exhausted and we end up in an accepting state, thenthis string is accepted by the automaton. Otherwise it is notaccepted. So $s$ is in the \emph{language accepted by theautomaton} $A(Q, q_0, F, \delta)$ iff\[\hat{\delta}(q_0, s) \in F \]\noindent I let you think about a definition that describesthe set of strings accepted by an automaton.While with DFAs it will always clear that given a characterwhat the next state is (potentially none), it will be usefulto relax this restriction. That means we have severalpotential successor states. We even allow ``silenttransitions'', also called epsilon-transitions. They allow usto go from one state to the next without having a characterconsumed. We label such silent transition with the letter$\epsilon$. The resulting construction is called a\emph{non-deterministic finite automaton} (NFA) given also asa four-tuple $A(Q, q_0, F, \rho)$ where\begin{itemize}\item $Q$ is a finite set of states\item $q_0$ is a start state\item $F$ are some accepting states with $F \subseteq Q$, and\item $\rho$ is a transition relation.\end{itemize}\noindentTwo typical examples of NFAs are\begin{center}\begin{tabular}[t]{c@{\hspace{9mm}}c}\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=0pt,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] {$\epsilon$} (q_1);\path[->] (q_0) edge node [left] {$\epsilon$} (q_2);\path[->] (q_0) edge [loop right] node {$a$} ();\path[->] (q_1) edge [loop above] node {$a$} ();\path[->] (q_2) edge [loop below] node {$b$} ();\end{tikzpicture} &\raisebox{20mm}{\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]\node[state,initial] (r_1) {$r_1$};\node[state] (r_2) [above=of r_1] {$r_2$};\node[state, accepting] (r_3) [right=of r_1] {$r_3$};\path[->] (r_1) edge node [below] {$b$} (r_3);\path[->] (r_2) edge [bend left] node [above] {$a$} (r_3);\path[->] (r_1) edge [bend left] node [left] {$\epsilon$} (r_2);\path[->] (r_2) edge [bend left] node [right] {$a$} (r_1);\end{tikzpicture}}\end{tabular}\end{center}\noindent There are, however, a number of points you shouldnote. Every DFA is a NFA, but not vice versa. The $\rho$ inNFAs is a transition \emph{relation} (DFAs have a transitionfunction). The difference between a function and a relation isthat a function has always a single output, while a relationgives, roughly speaking, several outputs. Look at the NFA onthe right-hand side above: if you are currently in the state$r_2$ and you read a character $a$, then you can transition toeither $r_1$ \emph{or} $r_3$. Which route you take is notdetermined. This means if we need to decide whether a stringis accepted by a NFA, we might have to explore allpossibilities. Also there is the special silent transition inNFAs. As mentioned already this transition means you do nothave to ``consume'' any part of the input string, but``silently'' change to a different state. In the left picture,for example, if you are in the starting state, you can silently move either to $q_1$ or $q_2$.\subsection*{Thompson Construction}The reason for introducing NFAs is that there is a relativelysimple (recursive) translation of regular expressions intoNFAs. Consider the simple regular expressions $\varnothing$,$\epsilon$ and $c$. They can be translated as follows:\begin{center}\begin{tabular}[t]{l@{\hspace{10mm}}l}\raisebox{1mm}{$\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}{$\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}{$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] {$c$} (q_1);\end{tikzpicture}\\\\\end{tabular}\end{center}\noindent The case for the sequence regular expression $r_1\cdot r_2$ is as follows: We are given by recursion twoautomata representing $r_1$ and $r_2$ respectively. \begin{center}\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$};\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{}$};\node[state, initial] (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{}$};\begin{pgfonlayer}{background}\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)] {};\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)] {};\node [yshift=2mm] at (1.north) {$r_1$};\node [yshift=2mm] at (2.north) {$r_2$};\end{pgfonlayer}\end{tikzpicture}\end{center}\noindent The first automaton has some accepting states. Weobtain an automaton for $r_1\cdot r_2$ by connecting theseaccepting states with $\epsilon$-transitions to the startingstate of the second automaton. By doing so we make themnon-accepting like so:\begin{center}\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$};\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{}$};\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{}$};\path[->] (t_1) edge node [above, pos=0.3] {$\epsilon$} (a_0);\path[->] (t_2) edge node [above] {$\epsilon$} (a_0);\path[->] (t_3) edge node [below] {$\epsilon$} (a_0);\begin{pgfonlayer}{background}\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};\end{pgfonlayer}\end{tikzpicture}\end{center}\noindent The case for the choice regular expression $r_1 +r_2$ is slightly different: We are given by recursion twoautomata representing $r_1$ and $r_2$ respectively. \begin{center}\begin{tikzpicture}[node distance=3mm, >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]\node at (0,0) (1) {$\mbox{}$};\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$};\node[state, initial] (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{}$};\begin{pgfonlayer}{background}\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};\node [yshift=3mm] at (1.north) {$r_1$};\node [yshift=3mm] at (2.north) {$r_2$};\end{pgfonlayer}\end{tikzpicture}\end{center}\noindent Each automaton has a single start state andpotentially several accepting states. We obtain a NFA for theregular expression $r_1 + r_2$ by introducing a new startingstate and connecting it with an $\epsilon$-transition to thetwo starting states above, like so\begin{center}\hspace{2cm}\begin{tikzpicture}[node distance=3mm, >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]\node at (0,0) [state, initial] (1) {$\mbox{}$};\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{}$};\path[->] (1) edge node [above] {$\epsilon$} (2);\path[->] (1) edge node [below] {$\epsilon$} (3);\begin{pgfonlayer}{background}\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};\node [yshift=3mm] at (3.north) {$r_1+ r_2$};\end{pgfonlayer}\end{tikzpicture}\end{center}\noindent Finally for the $*$-case we have an automaton for $r$\begin{center}\begin{tikzpicture}[node distance=3mm, >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]\node at (0,0) (1) {$\mbox{}$};\node[state, initial] (2) [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{}$};\begin{pgfonlayer}{background}\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};\node [yshift=3mm] at (1.north) {$r$};\end{pgfonlayer}\end{tikzpicture}\end{center}\noindent and connect its accepting states to a new startingstate via $\epsilon$-transitions. This new starting state isalso an accepting state, because $r^*$ can recognise theempty string. This gives the following automaton for $r^*$:\begin{center}\begin{tikzpicture}[node distance=3mm, >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};\node[state] (2) [right=16mm of 1] {$\mbox{}$};\node (a) [right=of 2] {$\ldots$};\node[state] (a1) [right=of a] {$\mbox{}$};\node[state] (a2) [above=of a1] {$\mbox{}$};\node[state] (a3) [below=of a1] {$\mbox{}$};\path[->] (1) edge node [above] {$\epsilon$} (2);\path[->] (a1) edge [bend left=45] node [above] {$\epsilon$} (1);\path[->] (a2) edge [bend right] node [below] {$\epsilon$} (1);\path[->] (a3) edge [bend left=45] node [below] {$\epsilon$} (1);\begin{pgfonlayer}{background}\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};\node [yshift=3mm] at (2.north) {$r^*$};\end{pgfonlayer}\end{tikzpicture}\end{center}\noindent This construction of a NFA from a regular expressionwas invented by Ken Thompson in 1968.\subsection*{Subset Construction}What is interesting that for every NFA we can find a DFA whichrecognises the same language. This can be done by the\emph{subset construction}. Consider again the NFA on the left, consisting of nodes labeled $0$, $1$ and $2$. \begin{center}\begin{tabular}{c@{\hspace{10mm}}c}\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=0pt, draw=blue!50,very thick,fill=blue!20}, baseline=0mm]\node[state,initial] (q_0) {$0$};\node[state] (q_1) [above=of q_0] {$1$};\node[state, accepting] (q_2) [below=of q_0] {$2$};\path[->] (q_0) edge node [left] {$\epsilon$} (q_1);\path[->] (q_0) edge node [left] {$\epsilon$} (q_2);\path[->] (q_0) edge [loop right] node {$a$} ();\path[->] (q_1) edge [loop above] node {$a$} ();\path[->] (q_2) edge [loop below] node {$b$} ();\end{tikzpicture}&\begin{tabular}{r|cl}nodes & $a$ & $b$\\\hline$\varnothing\phantom{\star}$ & $\varnothing$ & $\varnothing$\\$\{0\}\phantom{\star}$ & $\{0,1,2\}$ & $\{2\}$\\$\{1\}\phantom{\star}$ & $\{1\}$ & $\varnothing$\\$\{2\}\star$ & $\varnothing$ & $\{2\}$\\$\{0,1\}\phantom{\star}$ & $\{0,1,2\}$ & $\{2\}$\\$\{0,2\}\star$ & $\{0,1,2\}$ & $\{2\}$\\$\{1,2\}\star$ & $\{1\}$ & $\{2\}$\\s: $\{0,1,2\}\star$ & $\{0,1,2\}$ & $\{2\}$\\\end{tabular}\end{tabular}\end{center}\noindent The nodes of the DFA are given by calculating allsubsets of the set of nodes of the NFA (seen in the nodescolumn on the right). The table shows the transition functionfor the DFA. The first row states that $\varnothing$ is thesink node which has transitions for $a$ and $b$ to itself.The next three lines are calculated as follows: \begin{itemize}\item suppose you calculate the entry for the transition for $a$ and the node $\{0\}$\item start from the node $0$ in the NFA\item do as many $\epsilon$-transition as you can obtaining a set of nodes, in this case $\{0,1,2\}$\item filter out all notes that do not allow an $a$-transition from this set, this excludes $2$ which does not permit a $a$-transition\item from the remaining set, do as many $\epsilon$-transition as you can, this yields $\{0,1,2\}$ \item the resulting set specifies the transition from $\{0\}$ when given an $a$ \end{itemize}\noindent Similarly for the other entries in the rows for$\{0\}$, $\{1\}$ and $\{2\}$. The other rows are calculated byjust taking the union of the single node entries. For examplefor $a$ and $\{0,1\}$ we need to take the union of $\{0,1,2\}$(for $0$) and $\{1\}$ (for $1$). The starting state of the DFAcan be calculated from the starting state of the NFA, that is$0$, and then do as many $\epsilon$-transitions as possible.This gives $\{0,1,2\}$ which is the starting state of the DFA.One terminal states in the DFA are given by all sets thatcontain a $2$, which is the terminal state of the NFA. Thiscompletes the subset construction.There are two points to note: One is that the resulting DFAcontains a number of ``dead'' nodes that are never reachablefrom the starting state (that is that the calculated DFA inthis example is not a minimal DFA). Such dead nodes can besafely removed without changing the language that isrecognised by the DFA. Another point is that in some cases thesubset construction produces a DFA that does \emph{not}contain any dead nodes\ldots{}that means it calculates aminimal DFA. Which in turn means that in some cases the numberof nodes by going from NFAs to DFAs exponentially increases,namely by $2^n$ (which is the number of subsets you can formfor $n$ nodes). \subsection*{Brzozowski's Method}\subsection*{Automata Minimization}\subsection*{Regular Languages and Automata}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: