handouts/ho03.tex
changeset 268 18bef085a7ca
parent 251 5b5a68df6d16
child 269 83e6cb90216d
equal deleted inserted replaced
267:a1544b804d1e 268:18bef085a7ca
     1 \documentclass{article}
     1 \documentclass{article}
     2 \usepackage{../style}
     2 \usepackage{../style}
     3 \usepackage{../langs}
     3 \usepackage{../langs}
     4 
     4 \usepackage{../graphics}
     5 \usepackage{xcolor}
       
     6 \usepackage{tikz}
       
     7 \usetikzlibrary{arrows}
       
     8 \usetikzlibrary{automata}
       
     9 \usetikzlibrary{shapes}
       
    10 \usetikzlibrary{shadows}
       
    11 \usetikzlibrary{positioning}
       
    12 \usetikzlibrary{calc}
       
    13 \usetikzlibrary{fit}
       
    14 \usetikzlibrary{backgrounds}
       
    15 
     5 
    16 
     6 
    17 \begin{document}
     7 \begin{document}
    18 
     8 
    19 \section*{Handout 3}
     9 \section*{Handout 3 (Automata)}
    20 
    10 
    21 Let us have a closer look at automata and their relation to
    11 Every formal language course I know of bombards you first with
    22 regular expressions. This will help us to understand why the
    12 automata and then to a much, much smaller extend with regular
       
    13 expressions. As you can see, this course is turned upside
       
    14 down: regular expressions come first. The reason is that
       
    15 regular expressions are easier to reason about and the notion
       
    16 of derivatives, although already quite old, only became more
       
    17 widely known rather recently. Still let us in this lecture
       
    18 have a closer look at automata and their relation to regular
       
    19 expressions. This will help us with understanding why the
    23 regular expression matchers in Python and Ruby are so slow
    20 regular expression matchers in Python and Ruby are so slow
    24 with certain regular expressions. 
    21 with certain regular expressions. The central definition
    25 
    22 is:\medskip 
       
    23 
       
    24 \noindent 
    26 A \emph{deterministic finite automaton} (DFA), say $A$, is
    25 A \emph{deterministic finite automaton} (DFA), say $A$, is
    27 defined by a four-tuple written $A(Q, q_0, F, \delta)$ where
    26 defined by a four-tuple written $A(Q, q_0, F, \delta)$ where
    28 
    27 
    29 \begin{itemize}
    28 \begin{itemize}
    30 \item $Q$ is a set of states,
    29 \item $Q$ is a finite set of states,
    31 \item $q_0 \in Q$ is the start state,
    30 \item $q_0 \in Q$ is the start state,
    32 \item $F \subseteq Q$ are the accepting states, and
    31 \item $F \subseteq Q$ are the accepting states, and
    33 \item $\delta$ is the transition function.
    32 \item $\delta$ is the transition function.
    34 \end{itemize}
    33 \end{itemize}
    35 
    34 
    36 \noindent The transition function determines how to
    35 \noindent The transition function determines how to
    37 ``transition'' from one state to the next state with respect
    36 ``transition'' from one state to the next state with respect
    38 to a character. We have the assumption that these functions do
    37 to a character. We have the assumption that these transition
    39 not need to be defined everywhere: so it can be the case that
    38 functions do not need to be defined everywhere: so it can be
    40 given a character there is no next state, in which case we
    39 the case that given a character there is no next state, in
    41 need to raise a kind of ``raise an exception''. A typical
    40 which case we need to raise a kind of ``failure exception''. A
    42 example of a DFA is
    41 typical example of a DFA is
    43 
    42 
    44 \begin{center}
    43 \begin{center}
    45 \begin{tikzpicture}[>=stealth',very thick,auto,
    44 \begin{tikzpicture}[>=stealth',very thick,auto,
    46                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
    45                     every state/.style={minimum size=0pt,
       
    46                     inner sep=2pt,draw=blue!50,very thick,
       
    47                     fill=blue!20},scale=2]
    47 \node[state,initial]  (q_0)  {$q_0$};
    48 \node[state,initial]  (q_0)  {$q_0$};
    48 \node[state] (q_1) [right=of q_0] {$q_1$};
    49 \node[state] (q_1) [right=of q_0] {$q_1$};
    49 \node[state] (q_2) [below right=of q_0] {$q_2$};
    50 \node[state] (q_2) [below right=of q_0] {$q_2$};
    50 \node[state] (q_3) [right=of q_2] {$q_3$};
    51 \node[state] (q_3) [right=of q_2] {$q_3$};
    51 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};
    52 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};
    59 \path[->] (q_2) edge [loop left] node  {$b$} ();
    60 \path[->] (q_2) edge [loop left] node  {$b$} ();
    60 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {$b$} (q_0);
    61 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {$b$} (q_0);
    61 \end{tikzpicture}
    62 \end{tikzpicture}
    62 \end{center}
    63 \end{center}
    63 
    64 
    64 \noindent The accepting state $q_4$ is indicated with double
    65 \noindent In this graphical notation, the accepting state
    65 circles. It is possible that a DFA has no accepting states at
    66 $q_4$ is indicated with double circles. Note that there can be
    66 all, or that the starting state is also an accepting state. In
    67 more than one accepting state. It is also possible that a DFA
    67 the case above the transition function is defined everywhere
    68 has no accepting states at all, or that the starting state is
    68 and can be given as a table as follows:
    69 also an accepting state. In the case above the transition
       
    70 function is defined everywhere and can be given as a table as
       
    71 follows:
    69 
    72 
    70 \[
    73 \[
    71 \begin{array}{lcl}
    74 \begin{array}{lcl}
    72 (q_0, a) &\rightarrow& q_1\\
    75 (q_0, a) &\rightarrow& q_1\\
    73 (q_0, b) &\rightarrow& q_2\\
    76 (q_0, b) &\rightarrow& q_2\\
    80 (q_4, a) &\rightarrow& q_4\\
    83 (q_4, a) &\rightarrow& q_4\\
    81 (q_4, b) &\rightarrow& q_4\\
    84 (q_4, b) &\rightarrow& q_4\\
    82 \end{array}
    85 \end{array}
    83 \]
    86 \]
    84 
    87 
    85 \noindent We need to define the notion of what language is
    88 We need to define the notion of what language is accepted by
    86 accepted by an automaton. For this we lift the transition
    89 an automaton. For this we lift the transition function
    87 function $\delta$ from characters to strings as follows:
    90 $\delta$ from characters to strings as follows:
    88 
    91 
    89 \[
    92 \[
    90 \begin{array}{lcl}
    93 \begin{array}{lcl}
    91 \hat{\delta}(q, "")        & \dn & q\\
    94 \hat{\delta}(q, [])        & \dn & q\\
    92 \hat{\delta}(q, c\!::\!s) & \dn & \hat{\delta}(\delta(q, c), s)\\
    95 \hat{\delta}(q, c\!::\!s) & \dn & \hat{\delta}(\delta(q, c), s)\\
    93 \end{array}
    96 \end{array}
    94 \]
    97 \]
    95 
    98 
    96 \noindent Given a string this means we start in the starting
    99 \noindent This lifted transition function is often called
    97 state and take the first character of the string, follow to
   100 ``delta-hat''. Given a string, we start in the starting state
    98 the next sate, then take the second character and so on. Once
   101 and take the first character of the string, follow to the next
    99 the string is exhausted and we end up in an accepting state,
   102 sate, then take the second character and so on. Once the
   100 then this string is accepted. Otherwise it is not accepted. So
   103 string is exhausted and we end up in an accepting state, then
   101 $s$ in the \emph{language accepted by the automaton} $A(Q,
   104 this string is accepted by the automaton. Otherwise it is not
   102 q_0, F, \delta)$ iff
   105 accepted. So $s$ is in the \emph{language accepted by the
       
   106 automaton} $A(Q, q_0, F, \delta)$ iff
   103 
   107 
   104 \[
   108 \[
   105 \hat{\delta}(q_0, s) \in F 
   109 \hat{\delta}(q_0, s) \in F 
   106 \]
   110 \]
       
   111 
       
   112 \noindent I let you think about a definition that describes
       
   113 the set of strings accepted by an automaton.
   107   
   114   
   108 
   115 
   109 While with DFA it will always clear that given a character
   116 While with DFAs it will always clear that given a character
   110 what the next state is, it will be useful to relax this
   117 what the next state is (potentially none), it will be useful
   111 restriction. The resulting construction is called a
   118 to relax this restriction. That means we have several
   112 \emph{non-deterministic finite automaton} (NFA) given as a
   119 potential successor states. We even allow ``silent
   113 four-tuple $A(Q, q_0, F, \rho)$ where
   120 transitions'', also called epsilon-transitions. They allow us
       
   121 to go from one state to the next without having a character
       
   122 consumed. We label such silent transition with the letter
       
   123 $\epsilon$. The resulting construction is called a
       
   124 \emph{non-deterministic finite automaton} (NFA) given also as
       
   125 a four-tuple $A(Q, q_0, F, \rho)$ where
   114 
   126 
   115 \begin{itemize}
   127 \begin{itemize}
   116 \item $Q$ is a finite set of states
   128 \item $Q$ is a finite set of states
   117 \item $q_0$ is a start state
   129 \item $q_0$ is a start state
   118 \item $F$ are some accepting states with $F \subseteq Q$, and
   130 \item $F$ are some accepting states with $F \subseteq Q$, and
   147 \path[->] (r_2) edge [bend left] node  [right] {$a$} (r_1);
   159 \path[->] (r_2) edge [bend left] node  [right] {$a$} (r_1);
   148 \end{tikzpicture}}
   160 \end{tikzpicture}}
   149 \end{tabular}
   161 \end{tabular}
   150 \end{center}
   162 \end{center}
   151 
   163 
   152 \noindent There are a number of points you should note. Every
   164 \noindent There are, however, a number of points you should
   153 DFA is a NFA, but not vice versa. The $\rho$ in NFAs is a
   165 note. Every DFA is a NFA, but not vice versa. The $\rho$ in
   154 transition \emph{relation} (DFAs have a transition function).
   166 NFAs is a transition \emph{relation} (DFAs have a transition
   155 The difference between a function and a relation is that a
   167 function). The difference between a function and a relation is
   156 function has always a single output, while a relation gives,
   168 that a function has always a single output, while a relation
   157 roughly speaking, several outputs. Look at the NFA on the
   169 gives, roughly speaking, several outputs. Look at the NFA on
   158 right-hand side above: if you are currently in the state $r_2$
   170 the right-hand side above: if you are currently in the state
   159 and you read a character $a$, then you can transition to $r_1$
   171 $r_2$ and you read a character $a$, then you can transition to
   160 \emph{or} $r_3$. Which route you take is not determined. This
   172 either $r_1$ \emph{or} $r_3$. Which route you take is not
   161 means if we need to decide whether a string is accepted by a
   173 determined. This means if we need to decide whether a string
   162 NFA, we might have to explore all possibilities. Also there is
   174 is accepted by a NFA, we might have to explore all
   163 a special transition in NFAs which is called
   175 possibilities. Also there is the special silent transition in
   164 \emph{epsilon-transition} or \emph{silent transition}. This
   176 NFAs. As mentioned already this transition means you do not
   165 transition means you do not have to ``consume'' no part of the
   177 have to ``consume'' any part of the input string, but
   166 input string, but ``silently'' change to a different state.
   178 ``silently'' change to a different state. In the left picture,
       
   179 for example, if you are in the starting state, you can 
       
   180 silently move either to $q_1$ or $q_2$.
       
   181 
       
   182 
       
   183 \subsection*{Thompson Construction}
   167 
   184 
   168 The reason for introducing NFAs is that there is a relatively
   185 The reason for introducing NFAs is that there is a relatively
   169 simple (recursive) translation of regular expressions into
   186 simple (recursive) translation of regular expressions into
   170 NFAs. Consider the simple regular expressions $\varnothing$,
   187 NFAs. Consider the simple regular expressions $\varnothing$,
   171 $\epsilon$ and $c$. They can be translated as follows:
   188 $\epsilon$ and $c$. They can be translated as follows:
   326 \end{tikzpicture}
   343 \end{tikzpicture}
   327 \end{center}
   344 \end{center}
   328 
   345 
   329 \noindent and connect its accepting states to a new starting
   346 \noindent and connect its accepting states to a new starting
   330 state via $\epsilon$-transitions. This new starting state is
   347 state via $\epsilon$-transitions. This new starting state is
   331 also an accepting state, because $r^*$ can also recognise the
   348 also an accepting state, because $r^*$ can recognise the
   332 empty string. This gives the following automaton for $r^*$:
   349 empty string. This gives the following automaton for $r^*$:
   333 
   350 
   334 \begin{center}
   351 \begin{center}
   335 \begin{tikzpicture}[node distance=3mm,
   352 \begin{tikzpicture}[node distance=3mm,
   336                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
   353                              >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
   352 \end{center}
   369 \end{center}
   353 
   370 
   354 \noindent This construction of a NFA from a regular expression
   371 \noindent This construction of a NFA from a regular expression
   355 was invented by Ken Thompson in 1968.
   372 was invented by Ken Thompson in 1968.
   356 
   373 
       
   374 
       
   375 \subsection*{Subset Construction}
       
   376 
       
   377 What is interesting that for every NFA we can find a DFA which
       
   378 recognises the same language. This can be done by the
       
   379 \emph{subset construction}. Consider again the NFA on the 
       
   380 left, consisting of nodes labeled $0$, $1$ and $2$. 
       
   381 
       
   382 \begin{center}
       
   383 \begin{tabular}{c@{\hspace{10mm}}c}
       
   384 \begin{tikzpicture}[scale=0.7,>=stealth',very thick,
       
   385                     every state/.style={minimum size=0pt,
       
   386                     draw=blue!50,very thick,fill=blue!20},
       
   387                     baseline=0mm]
       
   388 \node[state,initial]  (q_0)  {$0$};
       
   389 \node[state] (q_1) [above=of q_0] {$1$};
       
   390 \node[state, accepting] (q_2) [below=of q_0] {$2$};
       
   391 \path[->] (q_0) edge node [left]  {$\epsilon$} (q_1);
       
   392 \path[->] (q_0) edge node [left]  {$\epsilon$} (q_2);
       
   393 \path[->] (q_0) edge [loop right] node  {$a$} ();
       
   394 \path[->] (q_1) edge [loop above] node  {$a$} ();
       
   395 \path[->] (q_2) edge [loop below] node  {$b$} ();
       
   396 \end{tikzpicture}
       
   397 &
       
   398 \begin{tabular}{r|cl}
       
   399 nodes & $a$ & $b$\\
       
   400 \hline
       
   401 $\varnothing\phantom{\star}$ & $\varnothing$ & $\varnothing$\\
       
   402 $\{0\}\phantom{\star}$       & $\{0,1,2\}$   & $\{2\}$\\
       
   403 $\{1\}\phantom{\star}$       & $\{1\}$       & $\varnothing$\\
       
   404 $\{2\}\star$  & $\varnothing$ & $\{2\}$\\
       
   405 $\{0,1\}\phantom{\star}$     & $\{0,1,2\}$   & $\{2\}$\\
       
   406 $\{0,2\}\star$ & $\{0,1,2\}$   & $\{2\}$\\
       
   407 $\{1,2\}\star$ & $\{1\}$       & $\{2\}$\\
       
   408 s: $\{0,1,2\}\star$ & $\{0,1,2\}$ & $\{2\}$\\
       
   409 \end{tabular}
       
   410 \end{tabular}
       
   411 \end{center}
       
   412 
       
   413 \noindent The nodes of the DFA are given by calculating all
       
   414 subsets of the set of nodes of the NFA (seen in the nodes
       
   415 column on the right). The table shows the transition function
       
   416 for the DFA. The first row states that $\varnothing$ is the
       
   417 sink node which has transitions for $a$ and $b$ to itself.
       
   418 The next three lines are calculated as follows: 
       
   419 
       
   420 \begin{itemize}
       
   421 \item suppose you calculate the entry for the transition for
       
   422       $a$ and the node $\{0\}$
       
   423 \item start from the node $0$ in the NFA
       
   424 \item do as many $\epsilon$-transition as you can obtaining a
       
   425       set of nodes, in this case $\{0,1,2\}$
       
   426 \item filter out all notes that do not allow an $a$-transition
       
   427       from this set, this excludes $2$ which does not permit a
       
   428       $a$-transition
       
   429 \item from the remaining set, do as many $\epsilon$-transition
       
   430       as you can, this yields $\{0,1,2\}$     
       
   431 \item the resulting set specifies the transition from $\{0\}$
       
   432       when given an $a$ 
       
   433 \end{itemize}
       
   434 
       
   435 \noindent Similarly for the other entries in the rows for
       
   436 $\{0\}$, $\{1\}$ and $\{2\}$. The other rows are calculated by
       
   437 just taking the union of the single node entries. For example
       
   438 for $a$ and $\{0,1\}$ we need to take the union of $\{0,1,2\}$
       
   439 (for $0$) and $\{1\}$ (for $1$). The starting state of the DFA
       
   440 can be calculated from the starting state of the NFA, that is
       
   441 $0$, and then do as many $\epsilon$-transitions as possible.
       
   442 This gives $\{0,1,2\}$ which is the starting state of the DFA.
       
   443 One terminal states in the DFA are given by all sets that
       
   444 contain a $2$, which is the terminal state of the NFA. This
       
   445 completes the subset construction.
       
   446 
       
   447 There are two points to note: One is that the resulting DFA
       
   448 contains a number of ``dead'' nodes that are never reachable
       
   449 from the starting state (that is that the calculated DFA in
       
   450 this example is not a minimal DFA). Such dead nodes can be
       
   451 safely removed without changing the language that is
       
   452 recognised by the DFA. Another point is that in some cases the
       
   453 subset construction produces a DFA that does \emph{not}
       
   454 contain any dead nodes\ldots{}that means it calculates a
       
   455 minimal DFA. Which in turn means that in some cases the number
       
   456 of nodes by going from NFAs to DFAs exponentially increases,
       
   457 namely by $2^n$ (which is the number of subsets you can form
       
   458 for $n$ nodes). 
       
   459 
       
   460 
       
   461 \subsection*{Brzozowski's Method}
       
   462 
       
   463 \subsection*{Automata Minimization}
       
   464 
       
   465 \subsection*{Regular Languages and Automata}
       
   466 
   357 \end{document}
   467 \end{document}
   358 
   468 
   359 %%% Local Variables: 
   469 %%% Local Variables: 
   360 %%% mode: latex
   470 %%% mode: latex
   361 %%% TeX-master: t
   471 %%% TeX-master: t