4 \usepackage{amssymb} |
4 \usepackage{amssymb} |
5 \usepackage{amsmath} |
5 \usepackage{amsmath} |
6 \usepackage[T1]{fontenc} |
6 \usepackage[T1]{fontenc} |
7 \usepackage{listings} |
7 \usepackage{listings} |
8 \usepackage{xcolor} |
8 \usepackage{xcolor} |
|
9 \usepackage{tikz} |
|
10 \usetikzlibrary{arrows} |
|
11 \usetikzlibrary{automata} |
|
12 \usetikzlibrary{shapes} |
|
13 \usetikzlibrary{shadows} |
|
14 \usetikzlibrary{positioning} |
|
15 \usetikzlibrary{calc} |
|
16 \usetikzlibrary{fit} |
|
17 \usetikzlibrary{backgrounds} |
9 |
18 |
10 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
19 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
11 |
20 |
12 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
21 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
13 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
22 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
47 |
56 |
48 \begin{document} |
57 \begin{document} |
49 |
58 |
50 \section*{Handout 3} |
59 \section*{Handout 3} |
51 |
60 |
|
61 Let us have a closer look at automata and their relation to regular expressions. This will help us to understand |
|
62 why the regular expression matchers in Python and Ruby are so slow with certain regular expressions. |
|
63 |
|
64 A deterministic finite automaton (DFA), say $A$, is defined by a four-tuple $A(Q, q_0, F, \delta)$ where |
|
65 |
|
66 \begin{itemize} |
|
67 \item $Q$ is a set of states, |
|
68 \item $q_0 \in Q$ is the start state, |
|
69 \item $F \subseteq Q$ are the accepting states, and |
|
70 \item $\delta$ is the transition function. |
|
71 \end{itemize} |
|
72 |
|
73 \noindent |
|
74 The transition function determines |
|
75 A typical example of a DFA is |
|
76 |
|
77 \begin{center} |
|
78 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
79 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
80 \node[state,initial] (q_0) {$q_0$}; |
|
81 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
82 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
83 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
84 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
85 \path[->] (q_0) edge node [above] {$a$} (q_1); |
|
86 \path[->] (q_1) edge node [above] {$a$} (q_4); |
|
87 \path[->] (q_4) edge [loop right] node {$a, b$} (); |
|
88 \path[->] (q_3) edge node [right] {$a$} (q_4); |
|
89 \path[->] (q_2) edge node [above] {$a$} (q_3); |
|
90 \path[->] (q_1) edge node [right] {$b$} (q_2); |
|
91 \path[->] (q_0) edge node [above] {$b$} (q_2); |
|
92 \path[->] (q_2) edge [loop left] node {$b$} (); |
|
93 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {$b$} (q_0); |
|
94 \end{tikzpicture} |
|
95 \end{center} |
52 |
96 |
53 \end{document} |
97 \end{document} |
54 |
98 |
55 %%% Local Variables: |
99 %%% Local Variables: |
56 %%% mode: latex |
100 %%% mode: latex |