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 |