662
|
1 |
% !TEX program = xelatex
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
\documentclass{article}
|
251
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../langs}
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
\usepackage{../graphics}
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
480
|
7 |
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
\begin{document}
|
874
|
9 |
\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2020, 2022}
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
|
482
|
11 |
\section*{Handout 3 (Finite Automata)}
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
|
488
|
13 |
|
480
|
14 |
Every formal language and compiler course I know of bombards you first
|
|
15 |
with automata and then to a much, much smaller extend with regular
|
|
16 |
expressions. As you can see, this course is turned upside down:
|
|
17 |
regular expressions come first. The reason is that regular expressions
|
|
18 |
are easier to reason about and the notion of derivatives, although
|
|
19 |
already quite old, only became more widely known rather
|
488
|
20 |
recently. Still, let us in this lecture have a closer look at automata
|
480
|
21 |
and their relation to regular expressions. This will help us with
|
|
22 |
understanding why the regular expression matchers in Python, Ruby and
|
485
|
23 |
Java are so slow with certain regular expressions. On the way we will
|
488
|
24 |
also see what are the limitations of regular
|
|
25 |
expressions. Unfortunately, they cannot be used for \emph{everything}.
|
482
|
26 |
|
|
27 |
|
|
28 |
\subsection*{Deterministic Finite Automata}
|
|
29 |
|
485
|
30 |
Lets start\ldots the central definition is:\medskip
|
142
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
\noindent
|
251
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
A \emph{deterministic finite automaton} (DFA), say $A$, is
|
484
|
34 |
given by a five-tuple written ${\cal A}(\varSigma, Qs, Q_0, F, \delta)$ where
|
142
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
\begin{itemize}
|
484
|
37 |
\item $\varSigma$ is an alphabet,
|
482
|
38 |
\item $Qs$ is a finite set of states,
|
|
39 |
\item $Q_0 \in Qs$ is the start state,
|
|
40 |
\item $F \subseteq Qs$ are the accepting states, and
|
142
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
\item $\delta$ is the transition function.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
|
490
|
44 |
\noindent I am sure you have seen this definition already
|
488
|
45 |
before. The transition function determines how to ``transition'' from
|
|
46 |
one state to the next state with respect to a character. We have the
|
|
47 |
assumption that these transition functions do not need to be defined
|
|
48 |
everywhere: so it can be the case that given a character there is no
|
|
49 |
next state, in which case we need to raise a kind of ``failure
|
483
|
50 |
exception''. That means actually we have \emph{partial} functions as
|
495
|
51 |
transitions---see the Scala implementation for DFAs later on. A
|
484
|
52 |
typical example of a DFA is
|
142
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\begin{tikzpicture}[>=stealth',very thick,auto,
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
inner sep=2pt,draw=blue!50,very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
fill=blue!20},scale=2]
|
482
|
59 |
\node[state,initial] (Q_0) {$Q_0$};
|
|
60 |
\node[state] (Q_1) [right=of Q_0] {$Q_1$};
|
|
61 |
\node[state] (Q_2) [below right=of Q_0] {$Q_2$};
|
|
62 |
\node[state] (Q_3) [right=of Q_2] {$Q_3$};
|
|
63 |
\node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$};
|
|
64 |
\path[->] (Q_0) edge node [above] {$a$} (Q_1);
|
|
65 |
\path[->] (Q_1) edge node [above] {$a$} (Q_4);
|
|
66 |
\path[->] (Q_4) edge [loop right] node {$a, b$} ();
|
|
67 |
\path[->] (Q_3) edge node [right] {$a$} (Q_4);
|
|
68 |
\path[->] (Q_2) edge node [above] {$a$} (Q_3);
|
|
69 |
\path[->] (Q_1) edge node [right] {$b$} (Q_2);
|
|
70 |
\path[->] (Q_0) edge node [above] {$b$} (Q_2);
|
|
71 |
\path[->] (Q_2) edge [loop left] node {$b$} ();
|
|
72 |
\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {$b$} (Q_0);
|
142
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
\end{center}
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
|
482
|
76 |
\noindent In this graphical notation, the accepting state $Q_4$ is
|
|
77 |
indicated with double circles. Note that there can be more than one
|
|
78 |
accepting state. It is also possible that a DFA has no accepting
|
485
|
79 |
state at all, or that the starting state is also an accepting
|
482
|
80 |
state. In the case above the transition function is defined everywhere
|
|
81 |
and can also be given as a table as follows:
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
\begin{array}{lcl}
|
482
|
85 |
(Q_0, a) &\rightarrow& Q_1\\
|
|
86 |
(Q_0, b) &\rightarrow& Q_2\\
|
|
87 |
(Q_1, a) &\rightarrow& Q_4\\
|
|
88 |
(Q_1, b) &\rightarrow& Q_2\\
|
|
89 |
(Q_2, a) &\rightarrow& Q_3\\
|
|
90 |
(Q_2, b) &\rightarrow& Q_2\\
|
|
91 |
(Q_3, a) &\rightarrow& Q_4\\
|
|
92 |
(Q_3, b) &\rightarrow& Q_0\\
|
|
93 |
(Q_4, a) &\rightarrow& Q_4\\
|
|
94 |
(Q_4, b) &\rightarrow& Q_4\\
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
\end{array}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
|
495
|
98 |
\noindent
|
|
99 |
Please check that this table represents the same transition function
|
|
100 |
as the graph above.
|
|
101 |
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
We need to define the notion of what language is accepted by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
an automaton. For this we lift the transition function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
$\delta$ from characters to strings as follows:
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
\begin{array}{lcl}
|
484
|
108 |
\widehat{\delta}(q, []) & \dn & q\\
|
|
109 |
\widehat{\delta}(q, c\!::\!s) & \dn & \widehat{\delta}(\delta(q, c), s)\\
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
\end{array}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
\noindent This lifted transition function is often called
|
485
|
114 |
\emph{delta-hat}. Given a string, we start in the starting state and
|
|
115 |
take the first character of the string, follow to the next state, then
|
|
116 |
take the second character and so on. Once the string is exhausted and
|
|
117 |
we end up in an accepting state, then this string is accepted by the
|
480
|
118 |
automaton. Otherwise it is not accepted. This also means that if along
|
|
119 |
the way we hit the case where the transition function $\delta$ is not
|
|
120 |
defined, we need to raise an error. In our implementation we will deal
|
485
|
121 |
with this case elegantly by using Scala's \texttt{Try}. Summing up: a
|
|
122 |
string $s$ is in the \emph{language accepted by the automaton} ${\cal
|
484
|
123 |
A}(\varSigma, Q, Q_0, F, \delta)$ iff
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
\[
|
484
|
126 |
\widehat{\delta}(Q_0, s) \in F
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
\]
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
|
488
|
129 |
\noindent I let you think about a definition that describes the set of
|
490
|
130 |
all strings accepted by a deterministic finite automaton.
|
480
|
131 |
|
|
132 |
\begin{figure}[p]
|
|
133 |
\small
|
753
|
134 |
\lstinputlisting[numbers=left,lastline=43]{../progs/automata/dfa.sc}
|
572
|
135 |
\caption{An implementation of DFAs in Scala using partial functions.
|
488
|
136 |
Note some subtleties: \texttt{deltas} implements the delta-hat
|
487
|
137 |
construction by lifting the (partial) transition function to lists
|
485
|
138 |
of characters. Since \texttt{delta} is given as a partial function,
|
|
139 |
it can obviously go ``wrong'' in which case the \texttt{Try} in
|
|
140 |
\texttt{accepts} catches the error and returns \texttt{false}---that
|
|
141 |
means the string is not accepted. The example \texttt{delta} in
|
753
|
142 |
Line 22--43 implements the DFA example shown earlier in the
|
485
|
143 |
handout.\label{dfa}}
|
480
|
144 |
\end{figure}
|
|
145 |
|
485
|
146 |
My take on an implementation of DFAs in Scala is given in
|
483
|
147 |
Figure~\ref{dfa}. As you can see, there are many features of the
|
482
|
148 |
mathematical definition that are quite closely reflected in the
|
|
149 |
code. In the DFA-class, there is a starting state, called
|
483
|
150 |
\texttt{start}, with the polymorphic type \texttt{A}. There is a
|
|
151 |
partial function \texttt{delta} for specifying the transitions---these
|
|
152 |
partial functions take a state (of polymorphic type \texttt{A}) and an
|
|
153 |
input (of polymorphic type \texttt{C}) and produce a new state (of
|
|
154 |
type \texttt{A}). For the moment it is OK to assume that \texttt{A} is
|
|
155 |
some arbitrary type for states and the input is just characters. (The
|
485
|
156 |
reason for not having concrete types, but polymorphic types for the
|
|
157 |
states and the input of DFAs will become clearer later on.)
|
483
|
158 |
|
485
|
159 |
The DFA-class has also an argument for specifying final states. In the
|
|
160 |
implementation it is not a set of states, as in the mathematical
|
|
161 |
definition, but a function from states to booleans (this function is
|
|
162 |
supposed to return true whenever a state is final; false
|
|
163 |
otherwise). While this boolean function is different from the sets of
|
753
|
164 |
states, Scala allows us to use sets for such functions (see Line 41 where
|
485
|
165 |
the DFA is initialised). Again it will become clear later on why I use
|
|
166 |
functions for final states, rather than sets.
|
|
167 |
|
|
168 |
The most important point in the implementation is that I use Scala's
|
484
|
169 |
partial functions for representing the transitions; alternatives would
|
|
170 |
have been \texttt{Maps} or even \texttt{Lists}. One of the main
|
|
171 |
advantages of using partial functions is that transitions can be quite
|
753
|
172 |
nicely defined by a series of \texttt{case} statements (see Lines 29
|
|
173 |
-- 39 for an example). If you need to represent an automaton with a
|
484
|
174 |
sink state (catch-all-state), you can use Scala's pattern matching and
|
|
175 |
write something like
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
|
490
|
177 |
{\small\begin{lstlisting}[language=Scala]
|
480
|
178 |
abstract class State
|
|
179 |
...
|
|
180 |
case object Sink extends State
|
|
181 |
|
|
182 |
val delta : (State, Char) :=> State =
|
|
183 |
{ case (S0, 'a') => S1
|
|
184 |
case (S1, 'a') => S2
|
|
185 |
case _ => Sink
|
|
186 |
}
|
|
187 |
\end{lstlisting}}
|
|
188 |
|
485
|
189 |
\noindent I let you think what the corresponding DFA looks like in the
|
497
|
190 |
graph notation. Also, I suggest you to tinker with the Scala code in
|
|
191 |
order to define the DFA that does not accept any string at all.
|
484
|
192 |
|
485
|
193 |
Finally, I let you ponder whether this is a good implementation of
|
|
194 |
DFAs or not. In doing so I hope you notice that the $\varSigma$ and
|
572
|
195 |
$Qs$ components (the alphabet and the set of \emph{finite} states,
|
485
|
196 |
respectively) are missing from the class definition. This means that
|
572
|
197 |
the implementation allows you to do some ``fishy'' things you are not
|
485
|
198 |
meant to do with DFAs. Which fishy things could that be?
|
480
|
199 |
|
482
|
200 |
|
|
201 |
|
|
202 |
\subsection*{Non-Deterministic Finite Automata}
|
|
203 |
|
485
|
204 |
Remember we want to find out what the relation is between regular
|
|
205 |
expressions and automata. To do this with DFAs is a bit unwieldy.
|
|
206 |
While with DFAs it is always clear that given a state and a character
|
|
207 |
what the next state is (potentially none), it will be convenient to
|
|
208 |
relax this restriction. That means we allow states to have several
|
482
|
209 |
potential successor states. We even allow more than one starting
|
484
|
210 |
state. The resulting construction is called a \emph{Non-Deterministic
|
485
|
211 |
Finite Automaton} (NFA) given also as a five-tuple ${\cal
|
|
212 |
A}(\varSigma, Qs, Q_{0s}, F, \rho)$ where
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
\begin{itemize}
|
484
|
215 |
\item $\varSigma$ is an alphabet,
|
482
|
216 |
\item $Qs$ is a finite set of states
|
|
217 |
\item $Q_{0s}$ is a set of start states ($Q_{0s} \subseteq Qs$)
|
|
218 |
\item $F$ are some accepting states with $F \subseteq Qs$, and
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
\item $\rho$ is a transition relation.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
221 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
222 |
\noindent
|
483
|
223 |
A typical example of a NFA is
|
482
|
224 |
|
|
225 |
% A NFA for (ab* + b)*a
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
\begin{center}
|
483
|
227 |
\begin{tikzpicture}[>=stealth',very thick, auto,
|
|
228 |
every state/.style={minimum size=0pt,inner sep=3pt,
|
|
229 |
draw=blue!50,very thick,fill=blue!20},scale=2]
|
482
|
230 |
\node[state,initial] (Q_0) {$Q_0$};
|
|
231 |
\node[state] (Q_1) [right=of Q_0] {$Q_1$};
|
|
232 |
\node[state, accepting] (Q_2) [right=of Q_1] {$Q_2$};
|
|
233 |
\path[->] (Q_0) edge [loop above] node {$b$} ();
|
|
234 |
\path[<-] (Q_0) edge node [below] {$b$} (Q_1);
|
|
235 |
\path[->] (Q_0) edge [bend left] node [above] {$a$} (Q_1);
|
|
236 |
\path[->] (Q_0) edge [bend right] node [below] {$a$} (Q_2);
|
|
237 |
\path[->] (Q_1) edge [loop above] node {$a,b$} ();
|
|
238 |
\path[->] (Q_1) edge node [above] {$a$} (Q_2);
|
|
239 |
\end{tikzpicture}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
|
482
|
242 |
\noindent
|
|
243 |
This NFA happens to have only one starting state, but in general there
|
495
|
244 |
could be more than one. Notice that in state $Q_0$ we might go to
|
|
245 |
state $Q_1$ \emph{or} to state $Q_2$ when receiving an $a$. Similarly
|
|
246 |
in state $Q_1$ and receiving an $a$, we can stay in state $Q_1$
|
|
247 |
\emph{or} go to $Q_2$. This kind of choice is not allowed with
|
|
248 |
DFAs. The downside of this choice in NFAs is that when it comes to
|
|
249 |
deciding whether a string is accepted by a NFA we potentially have to
|
|
250 |
explore all possibilities. I let you think which strings the above NFA
|
|
251 |
accepts.
|
482
|
252 |
|
|
253 |
|
485
|
254 |
There are a number of additional points you should note about
|
483
|
255 |
NFAs. Every DFA is a NFA, but not vice versa. The $\rho$ in NFAs is a
|
|
256 |
transition \emph{relation} (DFAs have a transition function). The
|
|
257 |
difference between a function and a relation is that a function has
|
|
258 |
always a single output, while a relation gives, roughly speaking,
|
|
259 |
several outputs. Look again at the NFA above: if you are currently in
|
|
260 |
the state $Q_1$ and you read a character $b$, then you can transition
|
|
261 |
to either $Q_0$ \emph{or} $Q_2$. Which route, or output, you take is
|
|
262 |
not determined. This non-determinism can be represented by a
|
|
263 |
relation.
|
482
|
264 |
|
483
|
265 |
My implementation of NFAs in Scala is shown in Figure~\ref{nfa}.
|
|
266 |
Perhaps interestingly, I do not actually use relations for my NFAs,
|
485
|
267 |
but use transition functions that return sets of states. DFAs have
|
|
268 |
partial transition functions that return a single state; my NFAs
|
488
|
269 |
return a set of states. I let you think about this representation for
|
485
|
270 |
NFA-transitions and how it corresponds to the relations used in the
|
487
|
271 |
mathematical definition of NFAs. An example of a transition function
|
488
|
272 |
in Scala for the NFA shown above is
|
482
|
273 |
|
490
|
274 |
{\small\begin{lstlisting}[language=Scala]
|
487
|
275 |
val nfa_delta : (State, Char) :=> Set[State] =
|
|
276 |
{ case (Q0, 'a') => Set(Q1, Q2)
|
|
277 |
case (Q0, 'b') => Set(Q0)
|
|
278 |
case (Q1, 'a') => Set(Q1, Q2)
|
|
279 |
case (Q1, 'b') => Set(Q0, Q1) }
|
|
280 |
\end{lstlisting}}
|
|
281 |
|
490
|
282 |
Like in the mathematical definition, \texttt{starts} is in
|
487
|
283 |
NFAs a set of states; \texttt{fins} is again a function from states to
|
485
|
284 |
booleans. The \texttt{next} function calculates the set of next states
|
|
285 |
reachable from a single state \texttt{q} by a character~\texttt{c}. In
|
|
286 |
case there is no such state---the partial transition function is
|
|
287 |
undefined---the empty set is returned (see function
|
753
|
288 |
\texttt{applyOrElse} in Lines 11 and 12). The function \texttt{nexts}
|
485
|
289 |
just lifts this function to sets of states.
|
|
290 |
|
484
|
291 |
\begin{figure}[p]
|
482
|
292 |
\small
|
753
|
293 |
\lstinputlisting[numbers=left,lastline=43]{../progs/automata/nfa.sc}
|
485
|
294 |
\caption{A Scala implementation of NFAs using partial functions.
|
|
295 |
Notice that the function \texttt{accepts} implements the
|
556
|
296 |
acceptance of a string in a breadth-first search fashion. This can be a costly
|
485
|
297 |
way of deciding whether a string is accepted or not in applications that need to handle
|
|
298 |
large NFAs and large inputs.\label{nfa}}
|
482
|
299 |
\end{figure}
|
|
300 |
|
485
|
301 |
Look very careful at the \texttt{accepts} and \texttt{deltas}
|
|
302 |
functions in NFAs and remember that when accepting a string by a NFA
|
484
|
303 |
we might have to explore all possible transitions (recall which state
|
753
|
304 |
to go to is not unique any more with NFAs\ldots{}we need to explore
|
485
|
305 |
potentially all next states). The implementation achieves this
|
487
|
306 |
exploration through a \emph{breadth-first search}. This is fine for
|
485
|
307 |
small NFAs, but can lead to real memory problems when the NFAs are
|
|
308 |
bigger and larger strings need to be processed. As result, some
|
|
309 |
regular expression matching engines resort to a \emph{depth-first
|
|
310 |
search} with \emph{backtracking} in unsuccessful cases. In our
|
|
311 |
implementation we can implement a depth-first version of
|
|
312 |
\texttt{accepts} using Scala's \texttt{exists}-function as follows:
|
483
|
313 |
|
|
314 |
|
490
|
315 |
{\small\begin{lstlisting}[language=Scala]
|
483
|
316 |
def search(q: A, s: List[C]) : Boolean = s match {
|
|
317 |
case Nil => fins(q)
|
485
|
318 |
case c::cs => next(q, c).exists(search(_, cs))
|
483
|
319 |
}
|
|
320 |
|
485
|
321 |
def accepts2(s: List[C]) : Boolean =
|
483
|
322 |
starts.exists(search(_, s))
|
|
323 |
\end{lstlisting}}
|
|
324 |
|
|
325 |
\noindent
|
487
|
326 |
This depth-first way of exploration seems to work quite efficiently in
|
|
327 |
many examples and is much less of a strain on memory. The problem is
|
|
328 |
that the backtracking can get ``catastrophic'' in some
|
|
329 |
examples---remember the catastrophic backtracking from earlier
|
|
330 |
lectures. This depth-first search with backtracking is the reason for
|
|
331 |
the abysmal performance of some regular expression matchings in Java,
|
|
332 |
Ruby and Python. I like to show you this in the next two sections.
|
482
|
333 |
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
334 |
|
490
|
335 |
\subsection*{Epsilon NFAs}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
336 |
|
485
|
337 |
In order to get an idea what calculations are performed by Java \&
|
|
338 |
friends, we need a method for transforming a regular expression into
|
753
|
339 |
a corresponding automaton. This automaton should accept exactly those strings that
|
485
|
340 |
are accepted by the regular expression. The simplest and most
|
753
|
341 |
well-known method for this is called the \emph{Thompson Construction},
|
485
|
342 |
after the Turing Award winner Ken Thompson. This method is by
|
487
|
343 |
recursion over regular expressions and depends on the non-determinism
|
488
|
344 |
in NFAs described in the previous section. You will see shortly why
|
487
|
345 |
this construction works well with NFAs, but is not so straightforward
|
|
346 |
with DFAs.
|
|
347 |
|
|
348 |
Unfortunately we are still one step away from our intended target
|
|
349 |
though---because this construction uses a version of NFAs that allows
|
|
350 |
``silent transitions''. The idea behind silent transitions is that
|
|
351 |
they allow us to go from one state to the next without having to
|
|
352 |
consume a character. We label such silent transition with the letter
|
|
353 |
$\epsilon$ and call the automata $\epsilon$NFAs. Two typical examples
|
|
354 |
of $\epsilon$NFAs are:
|
484
|
355 |
|
|
356 |
|
485
|
357 |
\begin{center}
|
|
358 |
\begin{tabular}[t]{c@{\hspace{9mm}}c}
|
|
359 |
\begin{tikzpicture}[>=stealth',very thick,
|
|
360 |
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
|
|
361 |
\node[state,initial] (Q_0) {$Q_0$};
|
|
362 |
\node[state] (Q_1) [above=of Q_0] {$Q_1$};
|
|
363 |
\node[state, accepting] (Q_2) [below=of Q_0] {$Q_2$};
|
|
364 |
\path[->] (Q_0) edge node [left] {$\epsilon$} (Q_1);
|
|
365 |
\path[->] (Q_0) edge node [left] {$\epsilon$} (Q_2);
|
|
366 |
\path[->] (Q_0) edge [loop right] node {$a$} ();
|
|
367 |
\path[->] (Q_1) edge [loop right] node {$a$} ();
|
|
368 |
\path[->] (Q_2) edge [loop right] node {$b$} ();
|
|
369 |
\end{tikzpicture} &
|
|
370 |
|
|
371 |
\raisebox{20mm}{
|
|
372 |
\begin{tikzpicture}[>=stealth',very thick,
|
|
373 |
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
|
|
374 |
\node[state,initial] (r_1) {$R_1$};
|
|
375 |
\node[state] (r_2) [above=of r_1] {$R_2$};
|
|
376 |
\node[state, accepting] (r_3) [right=of r_1] {$R_3$};
|
|
377 |
\path[->] (r_1) edge node [below] {$b$} (r_3);
|
|
378 |
\path[->] (r_2) edge [bend left] node [above] {$a$} (r_3);
|
|
379 |
\path[->] (r_1) edge [bend left] node [left] {$\epsilon$} (r_2);
|
|
380 |
\path[->] (r_2) edge [bend left] node [right] {$a$} (r_1);
|
|
381 |
\end{tikzpicture}}
|
|
382 |
\end{tabular}
|
|
383 |
\end{center}
|
|
384 |
|
|
385 |
\noindent
|
487
|
386 |
Consider the $\epsilon$NFA on the left-hand side: the
|
|
387 |
$\epsilon$-transitions mean you do not have to ``consume'' any part of
|
|
388 |
the input string, but ``silently'' change to a different state. In
|
|
389 |
this example, if you are in the starting state $Q_0$, you can silently
|
|
390 |
move either to $Q_1$ or $Q_2$. You can see that once you are in $Q_1$,
|
|
391 |
respectively $Q_2$, you cannot ``go back'' to the other states. So it
|
490
|
392 |
seems allowing $\epsilon$-transitions is a rather substantial
|
487
|
393 |
extension to NFAs. On first appearances, $\epsilon$-transitions might
|
|
394 |
even look rather strange, or even silly. To start with, silent
|
|
395 |
transitions make the decision whether a string is accepted by an
|
|
396 |
automaton even harder: with $\epsilon$NFAs we have to look whether we
|
|
397 |
can do first some $\epsilon$-transitions and then do a
|
|
398 |
``proper''-transition; and after any ``proper''-transition we again
|
|
399 |
have to check whether we can do again some silent transitions. Even
|
|
400 |
worse, if there is a silent transition pointing back to the same
|
|
401 |
state, then we have to be careful our decision procedure for strings
|
|
402 |
does not loop (remember the depth-first search for exploring all
|
|
403 |
states).
|
485
|
404 |
|
|
405 |
The obvious question is: Do we get anything in return for this hassle
|
|
406 |
with silent transitions? Well, we still have to work for it\ldots
|
|
407 |
unfortunately. If we were to follow the many textbooks on the
|
|
408 |
subject, we would now start with defining what $\epsilon$NFAs
|
|
409 |
are---that would require extending the transition relation of
|
490
|
410 |
NFAs. Next, we would show that the $\epsilon$NFAs are equivalent to
|
488
|
411 |
NFAs and so on. Once we have done all this on paper, we would need to
|
753
|
412 |
implement $\epsilon$NFAs. Let's try to take a shortcut instead. We are
|
488
|
413 |
not really interested in $\epsilon$NFAs; they are only a convenient
|
|
414 |
tool for translating regular expressions into automata. So we are not
|
|
415 |
going to implementing them explicitly, but translate them immediately
|
|
416 |
into NFAs (in a sense $\epsilon$NFAs are just a convenient API for
|
753
|
417 |
lazy people ;o). How does this translation work? Well we have to find
|
488
|
418 |
all transitions of the form
|
485
|
419 |
|
|
420 |
\[
|
|
421 |
q\stackrel{\epsilon}{\longrightarrow}\ldots\stackrel{\epsilon}{\longrightarrow}
|
|
422 |
\;\stackrel{a}{\longrightarrow}\;
|
|
423 |
\stackrel{\epsilon}{\longrightarrow}\ldots\stackrel{\epsilon}{\longrightarrow} q'
|
|
424 |
\]
|
|
425 |
|
753
|
426 |
\noindent where somewhere in the ``middle'' is an $a$-transition (for
|
|
427 |
a character, say, $a$). We replace them with
|
|
428 |
$q \stackrel{a}{\longrightarrow} q'$. Doing this to the $\epsilon$NFA
|
|
429 |
on the right-hand side above gives the NFA
|
485
|
430 |
|
|
431 |
\begin{center}
|
|
432 |
\begin{tikzpicture}[>=stealth',very thick,
|
|
433 |
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
|
|
434 |
\node[state,initial] (r_1) {$R_1$};
|
|
435 |
\node[state] (r_2) [above=of r_1] {$R_2$};
|
|
436 |
\node[state, accepting] (r_3) [right=of r_1] {$R_3$};
|
|
437 |
\path[->] (r_1) edge node [above] {$b$} (r_3);
|
|
438 |
\path[->] (r_2) edge [bend left] node [above] {$a$} (r_3);
|
|
439 |
\path[->] (r_1) edge [bend left] node [left] {$a$} (r_2);
|
|
440 |
\path[->] (r_2) edge [bend left] node [right] {$a$} (r_1);
|
|
441 |
\path[->] (r_1) edge [loop below] node {$a$} ();
|
|
442 |
\path[->] (r_1) edge [bend right] node [below] {$a$} (r_3);
|
|
443 |
\end{tikzpicture}
|
|
444 |
\end{center}
|
|
445 |
|
487
|
446 |
\noindent where the single $\epsilon$-transition is replaced by
|
|
447 |
three additional $a$-transitions. Please do the calculations yourself
|
|
448 |
and verify that I did not forget any transition.
|
|
449 |
|
|
450 |
So in what follows, whenever we are given an $\epsilon$NFA we will
|
488
|
451 |
replace it by an equivalent NFA. The Scala code for this translation
|
|
452 |
is given in Figure~\ref{enfa}. The main workhorse in this code is a
|
753
|
453 |
function that calculates a fixpoint of function (Lines 6--12). This
|
488
|
454 |
function is used for ``discovering'' which states are reachable by
|
487
|
455 |
$\epsilon$-transitions. Once no new state is discovered, a fixpoint is
|
|
456 |
reached. This is used for example when calculating the starting states
|
753
|
457 |
of an equivalent NFA (see Line 28): we start with all starting states
|
487
|
458 |
of the $\epsilon$NFA and then look for all additional states that can
|
|
459 |
be reached by $\epsilon$-transitions. We keep on doing this until no
|
|
460 |
new state can be reached. This is what the $\epsilon$-closure, named
|
|
461 |
in the code \texttt{ecl}, calculates. Similarly, an accepting state of
|
|
462 |
the NFA is when we can reach an accepting state of the $\epsilon$NFA
|
|
463 |
by $\epsilon$-transitions.
|
|
464 |
|
485
|
465 |
|
|
466 |
\begin{figure}[p]
|
|
467 |
\small
|
753
|
468 |
\lstinputlisting[numbers=left,lastline=43]{../progs/automata/enfa.sc}
|
485
|
469 |
|
|
470 |
\caption{A Scala function that translates $\epsilon$NFA into NFAs. The
|
490
|
471 |
transition function of $\epsilon$NFA takes as input an \texttt{Option[C]}.
|
485
|
472 |
\texttt{None} stands for an $\epsilon$-transition; \texttt{Some(c)}
|
488
|
473 |
for a ``proper'' transition consuming a character. The functions in
|
753
|
474 |
Lines 19--24 calculate
|
485
|
475 |
all states reachable by one or more $\epsilon$-transition for a given
|
753
|
476 |
set of states. The NFA is constructed in Lines 30--34.
|
|
477 |
Note the interesting commands in Lines 7 and 8: their purpose is
|
491
|
478 |
to ensure that \texttt{fixpT} is the tail-recursive version of
|
|
479 |
the fixpoint construction; otherwise we would quickly get a
|
|
480 |
stack-overflow exception, even on small examples, due to limitations
|
|
481 |
of the JVM.
|
|
482 |
\label{enfa}}
|
485
|
483 |
\end{figure}
|
|
484 |
|
487
|
485 |
Also look carefully how the transitions of $\epsilon$NFAs are
|
|
486 |
implemented. The additional possibility of performing silent
|
|
487 |
transitions is encoded by using \texttt{Option[C]} as the type for the
|
490
|
488 |
``input''. The \texttt{Some}s stand for ``proper'' transitions where
|
487
|
489 |
a character is consumed; \texttt{None} stands for
|
|
490 |
$\epsilon$-transitions. The transition functions for the two
|
|
491 |
$\epsilon$NFAs from the beginning of this section can be defined as
|
485
|
492 |
|
490
|
493 |
{\small\begin{lstlisting}[language=Scala]
|
487
|
494 |
val enfa_trans1 : (State, Option[Char]) :=> Set[State] =
|
|
495 |
{ case (Q0, Some('a')) => Set(Q0)
|
|
496 |
case (Q0, None) => Set(Q1, Q2)
|
|
497 |
case (Q1, Some('a')) => Set(Q1)
|
|
498 |
case (Q2, Some('b')) => Set(Q2) }
|
|
499 |
|
|
500 |
val enfa_trans2 : (State, Option[Char]) :=> Set[State] =
|
|
501 |
{ case (R1, Some('b')) => Set(R3)
|
|
502 |
case (R1, None) => Set(R2)
|
|
503 |
case (R2, Some('a')) => Set(R1, R3) }
|
|
504 |
\end{lstlisting}}
|
|
505 |
|
|
506 |
\noindent
|
|
507 |
I hope you agree now with my earlier statement that the $\epsilon$NFAs
|
|
508 |
are just an API for NFAs.
|
|
509 |
|
490
|
510 |
\subsection*{Thompson Construction}
|
487
|
511 |
|
|
512 |
Having the translation of $\epsilon$NFAs to NFAs in place, we can
|
|
513 |
finally return to the problem of translating regular expressions into
|
|
514 |
equivalent NFAs. Recall that by equivalent we mean that the NFAs
|
485
|
515 |
recognise the same language. Consider the simple regular expressions
|
|
516 |
$\ZERO$, $\ONE$ and $c$. They can be translated into equivalent NFAs
|
|
517 |
as follows:
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
518 |
|
488
|
519 |
\begin{equation}\mbox{
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
520 |
\begin{tabular}[t]{l@{\hspace{10mm}}l}
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
521 |
\raisebox{1mm}{$\ZERO$} &
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
522 |
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
|
482
|
523 |
\node[state, initial] (Q_0) {$\mbox{}$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
524 |
\end{tikzpicture}\\\\
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
525 |
\raisebox{1mm}{$\ONE$} &
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
526 |
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
|
482
|
527 |
\node[state, initial, accepting] (Q_0) {$\mbox{}$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
528 |
\end{tikzpicture}\\\\
|
487
|
529 |
\raisebox{3mm}{$c$} &
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
530 |
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
|
482
|
531 |
\node[state, initial] (Q_0) {$\mbox{}$};
|
|
532 |
\node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$};
|
|
533 |
\path[->] (Q_0) edge node [below] {$c$} (Q_1);
|
487
|
534 |
\end{tikzpicture}\\
|
488
|
535 |
\end{tabular}}\label{simplecases}
|
|
536 |
\end{equation}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
537 |
|
487
|
538 |
\noindent
|
|
539 |
I let you think whether the NFAs can match exactly those strings the
|
|
540 |
regular expressions can match. To do this translation in code we need
|
495
|
541 |
a way to construct states ``programatically''...and as an additional
|
|
542 |
constraint Scala needs to recognise that these states are being distinct.
|
487
|
543 |
For this I implemented in Figure~\ref{thompson1} a class
|
|
544 |
\texttt{TState} that includes a counter and a companion object that
|
488
|
545 |
increases this counter whenever a new state is created.\footnote{You might
|
|
546 |
have to read up what \emph{companion objects} do in Scala.}
|
487
|
547 |
|
485
|
548 |
\begin{figure}[p]
|
|
549 |
\small
|
753
|
550 |
\lstinputlisting[numbers=left,linerange={1-20}]{../progs/automata/thompson.sc}
|
|
551 |
\hspace{5mm}\texttt{\dots}
|
|
552 |
\lstinputlisting[numbers=left,linerange={28-45},firstnumber=28]{../progs/automata/thompson.sc}
|
|
553 |
\caption{The first part of the Thompson Construction. Lines 10--19
|
488
|
554 |
implement a way of how to create new states that are all
|
487
|
555 |
distinct by virtue of a counter. This counter is
|
|
556 |
increased in the companion object of \texttt{TState}
|
753
|
557 |
whenever a new state is created. The code in Lines 38--45
|
488
|
558 |
constructs NFAs for the simple regular expressions $\ZERO$, $\ONE$ and $c$.
|
495
|
559 |
Compare this code with the pictures given in \eqref{simplecases} on
|
|
560 |
Page~\pageref{simplecases}.
|
487
|
561 |
\label{thompson1}}
|
485
|
562 |
\end{figure}
|
|
563 |
|
487
|
564 |
\begin{figure}[p]
|
|
565 |
\small
|
753
|
566 |
\lstinputlisting[numbers=left,firstline=48,firstnumber=48,lastline=85]{../progs/automata/thompson.sc}
|
487
|
567 |
\caption{The second part of the Thompson Construction implementing
|
490
|
568 |
the composition of NFAs according to $\cdot$, $+$ and ${}^*$.
|
753
|
569 |
The implicit class (Lines 48--54) about rich partial functions
|
487
|
570 |
implements the infix operation \texttt{+++} which
|
753
|
571 |
combines an $\epsilon$NFA transition with an NFA transition
|
495
|
572 |
(both are given as partial functions---but with different type!).\label{thompson2}}
|
487
|
573 |
\end{figure}
|
485
|
574 |
|
488
|
575 |
The case for the sequence regular expression $r_1 \cdot r_2$ is a bit more
|
489
|
576 |
complicated: Say, we are given by recursion two NFAs representing the regular
|
488
|
577 |
expressions $r_1$ and $r_2$ respectively.
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
578 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
579 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
580 |
\begin{tikzpicture}[node distance=3mm,
|
488
|
581 |
>=stealth',very thick,
|
|
582 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
|
482
|
583 |
\node[state, initial] (Q_0) {$\mbox{}$};
|
488
|
584 |
\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
|
|
585 |
\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
|
|
586 |
\node (R_1) [right=of Q_0] {$\ldots$};
|
|
587 |
\node[state, accepting] (T_1) [right=of R_1] {$\mbox{}$};
|
|
588 |
\node[state, accepting] (T_2) [above=of T_1] {$\mbox{}$};
|
|
589 |
\node[state, accepting] (T_3) [below=of T_1] {$\mbox{}$};
|
|
590 |
|
|
591 |
\node (A_0) [right=2.5cm of T_1] {$\mbox{}$};
|
|
592 |
\node[state, initial] (A_01) [above=1mm of A_0] {$\mbox{}$};
|
|
593 |
\node[state, initial] (A_02) [below=1mm of A_0] {$\mbox{}$};
|
|
594 |
|
|
595 |
\node (b_1) [right=of A_0] {$\ldots$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
596 |
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
597 |
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
598 |
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
599 |
\begin{pgfonlayer}{background}
|
488
|
600 |
\node (1) [rounded corners, inner sep=1mm, thick,
|
|
601 |
draw=black!60, fill=black!20, fit= (Q_0) (R_1) (T_1) (T_2) (T_3)] {};
|
|
602 |
\node (2) [rounded corners, inner sep=1mm, thick,
|
|
603 |
draw=black!60, fill=black!20, fit= (A_0) (b_1) (c_1) (c_2) (c_3)] {};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
604 |
\node [yshift=2mm] at (1.north) {$r_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
605 |
\node [yshift=2mm] at (2.north) {$r_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
606 |
\end{pgfonlayer}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
607 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
608 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
609 |
|
488
|
610 |
\noindent The first NFA has some accepting states and the second some
|
489
|
611 |
starting states. We obtain an $\epsilon$NFA for $r_1\cdot r_2$ by
|
|
612 |
connecting the accepting states of the first NFA with
|
|
613 |
$\epsilon$-transitions to the starting states of the second
|
|
614 |
automaton. By doing so we make the accepting states of the first NFA
|
|
615 |
to be non-accepting like so:
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
616 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
617 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
618 |
\begin{tikzpicture}[node distance=3mm,
|
488
|
619 |
>=stealth',very thick,
|
|
620 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
|
482
|
621 |
\node[state, initial] (Q_0) {$\mbox{}$};
|
488
|
622 |
\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
|
|
623 |
\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
|
482
|
624 |
\node (r_1) [right=of Q_0] {$\ldots$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
625 |
\node[state] (t_1) [right=of r_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
626 |
\node[state] (t_2) [above=of t_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
627 |
\node[state] (t_3) [below=of t_1] {$\mbox{}$};
|
488
|
628 |
|
|
629 |
\node (A_0) [right=2.5cm of t_1] {$\mbox{}$};
|
|
630 |
\node[state] (A_01) [above=1mm of A_0] {$\mbox{}$};
|
|
631 |
\node[state] (A_02) [below=1mm of A_0] {$\mbox{}$};
|
|
632 |
|
|
633 |
\node (b_1) [right=of A_0] {$\ldots$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
634 |
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
635 |
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
636 |
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
|
488
|
637 |
\path[->] (t_1) edge (A_01);
|
492
|
638 |
\path[->] (t_2) edge node [above] {$\epsilon$s} (A_01);
|
488
|
639 |
\path[->] (t_3) edge (A_01);
|
|
640 |
\path[->] (t_1) edge (A_02);
|
|
641 |
\path[->] (t_2) edge (A_02);
|
492
|
642 |
\path[->] (t_3) edge node [below] {$\epsilon$s} (A_02);
|
488
|
643 |
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
644 |
\begin{pgfonlayer}{background}
|
488
|
645 |
\node (3) [rounded corners, inner sep=1mm, thick,
|
|
646 |
draw=black!60, fill=black!20, fit= (Q_0) (c_1) (c_2) (c_3)] {};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
647 |
\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
648 |
\end{pgfonlayer}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
649 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
650 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
651 |
|
489
|
652 |
\noindent The idea behind this construction is that the start of any
|
|
653 |
string is first recognised by the first NFA, then we silently change
|
|
654 |
to the second NFA; the ending of the string is recognised by the
|
|
655 |
second NFA...just like matching of a string by the regular expression
|
490
|
656 |
$r_1\cdot r_2$. The Scala code for this construction is given in
|
753
|
657 |
Figure~\ref{thompson2} in Lines 57--65. The starting states of the
|
489
|
658 |
$\epsilon$NFA are the starting states of the first NFA (corresponding
|
|
659 |
to $r_1$); the accepting function is the accepting function of the
|
|
660 |
second NFA (corresponding to $r_2$). The new transition function is
|
|
661 |
all the ``old'' transitions plus the $\epsilon$-transitions connecting
|
|
662 |
the accepting states of the first NFA to the starting states of the
|
753
|
663 |
second NFA (Lines 59 and 60). The $\epsilon$NFA is then immediately
|
489
|
664 |
translated in a NFA.
|
|
665 |
|
|
666 |
|
490
|
667 |
The case for the alternative regular expression $r_1 + r_2$ is
|
|
668 |
slightly different: We are given by recursion two NFAs representing
|
|
669 |
$r_1$ and $r_2$ respectively. Each NFA has some starting states and
|
753
|
670 |
some accepting states. We obtain a NFA for the regular expression
|
|
671 |
$r_1 + r_2$ by composing the transition functions (this crucially
|
|
672 |
depends on knowing that the states of each component NFA are
|
|
673 |
distinct---recall we implemented for this to hold by some bespoke code
|
|
674 |
for \texttt{TState}s). We also need to combine the starting states and
|
|
675 |
accepting functions appropriately.
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
676 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
677 |
\begin{center}
|
490
|
678 |
\begin{tabular}[t]{ccc}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
679 |
\begin{tikzpicture}[node distance=3mm,
|
488
|
680 |
>=stealth',very thick,
|
490
|
681 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
|
|
682 |
baseline=(current bounding box.center)]
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
683 |
\node at (0,0) (1) {$\mbox{}$};
|
489
|
684 |
\node (2) [above=10mm of 1] {};
|
|
685 |
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
|
|
686 |
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
|
|
687 |
\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
688 |
|
489
|
689 |
\node (a) [right=of 2] {$\ldots\,$};
|
|
690 |
\node (a1) [right=of a] {$$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
691 |
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
692 |
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
693 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
694 |
\node (b) [right=of 3] {$\ldots$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
695 |
\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
696 |
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
697 |
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
698 |
\begin{pgfonlayer}{background}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
699 |
\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
700 |
\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
701 |
\node [yshift=3mm] at (1.north) {$r_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
702 |
\node [yshift=3mm] at (2.north) {$r_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
703 |
\end{pgfonlayer}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
704 |
\end{tikzpicture}
|
490
|
705 |
&
|
|
706 |
\mbox{}\qquad\tikz{\draw[>=stealth,line width=2mm,->] (0,0) -- (1, 0)}\quad\mbox{}
|
|
707 |
&
|
489
|
708 |
\begin{tikzpicture}[node distance=3mm,
|
|
709 |
>=stealth',very thick,
|
490
|
710 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
|
|
711 |
baseline=(current bounding box.center)]
|
489
|
712 |
\node at (0,0) (1) {$\mbox{}$};
|
|
713 |
\node (2) [above=10mm of 1] {$$};
|
|
714 |
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
|
|
715 |
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
|
|
716 |
\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
717 |
|
489
|
718 |
\node (a) [right=of 2] {$\ldots\,$};
|
|
719 |
\node (a1) [right=of a] {$$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
720 |
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
721 |
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
722 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
723 |
\node (b) [right=of 3] {$\ldots$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
724 |
\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
725 |
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
726 |
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
727 |
|
489
|
728 |
%\path[->] (1) edge node [above] {$\epsilon$} (2);
|
|
729 |
%\path[->] (1) edge node [below] {$\epsilon$} (3);
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
730 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
731 |
\begin{pgfonlayer}{background}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
732 |
\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
733 |
\node [yshift=3mm] at (3.north) {$r_1+ r_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
734 |
\end{pgfonlayer}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
735 |
\end{tikzpicture}
|
490
|
736 |
\end{tabular}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
737 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
738 |
|
489
|
739 |
\noindent The code for this construction is in Figure~\ref{thompson2}
|
753
|
740 |
in Lines 67--75.
|
490
|
741 |
|
|
742 |
Finally for the $*$-case we have a NFA for $r$ and connect its
|
|
743 |
accepting states to a new starting state via
|
|
744 |
$\epsilon$-transitions. This new starting state is also an accepting
|
|
745 |
state, because $r^*$ can recognise the empty string.
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
746 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
747 |
\begin{center}
|
495
|
748 |
\begin{tabular}[b]{@{}ccc@{}}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
749 |
\begin{tikzpicture}[node distance=3mm,
|
490
|
750 |
>=stealth',very thick,
|
|
751 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
|
|
752 |
baseline=(current bounding box.north)]
|
495
|
753 |
\node (2) {$\mbox{}$};
|
|
754 |
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
|
|
755 |
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
756 |
\node (a) [right=of 2] {$\ldots$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
757 |
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
758 |
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
759 |
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
760 |
\begin{pgfonlayer}{background}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
761 |
\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
762 |
\node [yshift=3mm] at (1.north) {$r$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
763 |
\end{pgfonlayer}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
764 |
\end{tikzpicture}
|
490
|
765 |
&
|
|
766 |
\raisebox{-16mm}{\;\tikz{\draw[>=stealth,line width=2mm,->] (0,0) -- (1, 0)}}
|
|
767 |
&
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
768 |
\begin{tikzpicture}[node distance=3mm,
|
489
|
769 |
>=stealth',very thick,
|
490
|
770 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
|
|
771 |
baseline=(current bounding box.north)]
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
772 |
\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};
|
495
|
773 |
\node (2) [right=16mm of 1] {$\mbox{}$};
|
|
774 |
\node[state] (4) [above=1mm of 2] {$\mbox{}$};
|
|
775 |
\node[state] (5) [below=1mm of 2] {$\mbox{}$};
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
776 |
\node (a) [right=of 2] {$\ldots$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
777 |
\node[state] (a1) [right=of a] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
778 |
\node[state] (a2) [above=of a1] {$\mbox{}$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
779 |
\node[state] (a3) [below=of a1] {$\mbox{}$};
|
495
|
780 |
\path[->] (1) edge node [below] {$\epsilon$} (4);
|
|
781 |
\path[->] (1) edge node [below] {$\epsilon$} (5);
|
|
782 |
\path[->] (a1) edge [bend left=45] node [below] {$\epsilon$} (1);
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
783 |
\path[->] (a2) edge [bend right] node [below] {$\epsilon$} (1);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
784 |
\path[->] (a3) edge [bend left=45] node [below] {$\epsilon$} (1);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
785 |
\begin{pgfonlayer}{background}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
786 |
\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
787 |
\node [yshift=3mm] at (2.north) {$r^*$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
788 |
\end{pgfonlayer}
|
490
|
789 |
\end{tikzpicture}
|
|
790 |
\end{tabular}
|
143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
791 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
792 |
|
490
|
793 |
\noindent
|
753
|
794 |
The corresponding code is in Figure~\ref{thompson2} in Lines 77--85)
|
489
|
795 |
|
753
|
796 |
To sum up, you can see in the sequence and star cases the need for
|
|
797 |
silent $\epsilon$-transitions. Otherwise this construction just
|
|
798 |
becomes awkward. Similarly the alternative case shows the need of the
|
|
799 |
NFA-nondeterminism. It looks non-obvious to form the `alternative'
|
|
800 |
composition of two DFAs, because DFA do not allow several starting and
|
|
801 |
successor states. All these constructions can now be put together in
|
|
802 |
the following recursive function:
|
489
|
803 |
|
|
804 |
|
490
|
805 |
{\small\begin{lstlisting}[language=Scala]
|
|
806 |
def thompson(r: Rexp) : NFAt = r match {
|
488
|
807 |
case ZERO => NFA_ZERO()
|
|
808 |
case ONE => NFA_ONE()
|
|
809 |
case CHAR(c) => NFA_CHAR(c)
|
|
810 |
case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2))
|
|
811 |
case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2))
|
|
812 |
case STAR(r1) => NFA_STAR(thompson(r1))
|
|
813 |
}
|
|
814 |
\end{lstlisting}}
|
|
815 |
|
489
|
816 |
\noindent
|
490
|
817 |
It calculates a NFA from a regular expressions. At last we can run
|
|
818 |
NFAs for the our evil regular expression examples. The graph on the
|
|
819 |
left shows that when translating a regular expression such as
|
753
|
820 |
$a^{?\{n\}} \cdot a^{\{n\}}$ into a NFA, the size can blow up and then
|
|
821 |
even the relative fast (on small examples) breadth-first search can be
|
|
822 |
slow\ldots the red line maxes out at about 15 $n$s.
|
|
823 |
|
|
824 |
|
|
825 |
The graph on the right shows that with `evil' regular expressions also
|
|
826 |
the depth-first search can be abysmally slow. Even if the graphs not
|
|
827 |
completely overlap with the curves of Python, Ruby and Java, they are
|
|
828 |
similar enough.
|
489
|
829 |
|
488
|
830 |
|
|
831 |
\begin{center}
|
|
832 |
\begin{tabular}{@{\hspace{-1mm}}c@{\hspace{1mm}}c@{}}
|
|
833 |
\begin{tikzpicture}
|
|
834 |
\begin{axis}[
|
490
|
835 |
title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings
|
489
|
836 |
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
|
490
|
837 |
title style={yshift=-2ex},
|
489
|
838 |
xlabel={$n$},
|
|
839 |
x label style={at={(1.05,0.0)}},
|
|
840 |
ylabel={time in secs},
|
|
841 |
enlargelimits=false,
|
|
842 |
xtick={0,5,...,30},
|
|
843 |
xmax=33,
|
|
844 |
ymax=35,
|
|
845 |
ytick={0,5,...,30},
|
|
846 |
scaled ticks=false,
|
|
847 |
axis lines=left,
|
|
848 |
width=5.5cm,
|
490
|
849 |
height=4cm,
|
|
850 |
legend entries={Python,Ruby, breadth-first NFA},
|
|
851 |
legend style={at={(0.5,-0.25)},anchor=north,font=\small},
|
489
|
852 |
legend cell align=left]
|
|
853 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
|
|
854 |
\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
|
|
855 |
% breath-first search in NFAs
|
|
856 |
\addplot[red,mark=*, mark options={fill=white}] table {
|
|
857 |
1 0.00586
|
|
858 |
2 0.01209
|
|
859 |
3 0.03076
|
|
860 |
4 0.08269
|
|
861 |
5 0.12881
|
|
862 |
6 0.25146
|
|
863 |
7 0.51377
|
|
864 |
8 0.89079
|
|
865 |
9 1.62802
|
|
866 |
10 3.05326
|
|
867 |
11 5.92437
|
|
868 |
12 11.67863
|
|
869 |
13 24.00568
|
|
870 |
};
|
|
871 |
\end{axis}
|
|
872 |
\end{tikzpicture}
|
|
873 |
&
|
|
874 |
\begin{tikzpicture}
|
|
875 |
\begin{axis}[
|
490
|
876 |
title={Graph: $(a^*)^* \cdot b$ and strings
|
488
|
877 |
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
|
490
|
878 |
title style={yshift=-2ex},
|
488
|
879 |
xlabel={$n$},
|
|
880 |
x label style={at={(1.05,0.0)}},
|
|
881 |
ylabel={time in secs},
|
|
882 |
enlargelimits=false,
|
|
883 |
xtick={0,5,...,30},
|
|
884 |
xmax=33,
|
|
885 |
ymax=35,
|
|
886 |
ytick={0,5,...,30},
|
|
887 |
scaled ticks=false,
|
|
888 |
axis lines=left,
|
|
889 |
width=5.5cm,
|
490
|
890 |
height=4cm,
|
753
|
891 |
legend entries={Python, Java 8, depth-first NFA},
|
490
|
892 |
legend style={at={(0.5,-0.25)},anchor=north,font=\small},
|
488
|
893 |
legend cell align=left]
|
|
894 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
|
|
895 |
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
|
|
896 |
% depth-first search in NFAs
|
|
897 |
\addplot[red,mark=*, mark options={fill=white}] table {
|
|
898 |
1 0.00605
|
|
899 |
2 0.03086
|
|
900 |
3 0.11994
|
|
901 |
4 0.45389
|
|
902 |
5 2.06192
|
|
903 |
6 8.04894
|
|
904 |
7 32.63549
|
|
905 |
};
|
|
906 |
\end{axis}
|
|
907 |
\end{tikzpicture}
|
|
908 |
\end{tabular}
|
|
909 |
\end{center}
|
|
910 |
|
753
|
911 |
\noindent
|
|
912 |
OK\ldots now you know why regular expression matchers in those
|
|
913 |
languages are sometimes so slow. A bit surprising, don't you agree?
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
914 |
|
490
|
915 |
\subsection*{Subset Construction}
|
|
916 |
|
491
|
917 |
Of course, some developers of regular expression matchers are aware of
|
|
918 |
these problems with sluggish NFAs and try to address them. One common
|
|
919 |
technique for alleviating the problem I like to show you in this
|
|
920 |
section. This will also explain why we insisted on polymorphic types in
|
|
921 |
our DFA code (remember I used \texttt{A} and \texttt{C} for the types
|
|
922 |
of states and the input, see Figure~\ref{dfa} on
|
|
923 |
Page~\pageref{dfa}).\bigskip
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
924 |
|
490
|
925 |
\noindent
|
662
|
926 |
To start, remember that we did not bother with defining and implementing
|
|
927 |
$\epsilon$NFAs: we immediately translated them into equivalent NFAs.
|
|
928 |
Equivalent in the sense of accepting the same language (though we only
|
|
929 |
claimed this and did not prove it rigorously). Remember also that NFAs
|
|
930 |
have non-deterministic transitions defined as a relation, or
|
|
931 |
alternatively my Scala implementation used transition functions returning sets of
|
|
932 |
states. This non-determinism is crucial for the Thompson Construction
|
|
933 |
to work (recall the cases for $\cdot$, $+$ and ${}^*$). But this
|
|
934 |
non-determinism makes it harder with NFAs to decide when a string is
|
|
935 |
accepted or not; whereas such a decision is rather straightforward with
|
|
936 |
DFAs: recall their transition function is a ``real'' function that returns
|
|
937 |
a single state. So with DFAs we do not have to search at all. What is
|
|
938 |
perhaps interesting is the fact that for every NFA we can find a DFA
|
|
939 |
that also recognises the same language. This might sound a bit
|
|
940 |
paradoxical: NFA $\rightarrow$ decision of acceptance hard; DFA
|
|
941 |
$\rightarrow$ decision easy. But this \emph{is} true\ldots but of course
|
753
|
942 |
there is always a caveat---nothing ever is for free in life. Let's see what this
|
|
943 |
actually means.
|
488
|
944 |
|
491
|
945 |
There are actually a number of methods for transforming a NFA into
|
|
946 |
an equivalent DFA, but the most famous one is the \emph{subset
|
490
|
947 |
construction}. Consider the following NFA where the states are
|
491
|
948 |
labelled with $0$, $1$ and $2$.
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
949 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
950 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
951 |
\begin{tabular}{c@{\hspace{10mm}}c}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
952 |
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
953 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
954 |
draw=blue!50,very thick,fill=blue!20},
|
490
|
955 |
baseline=(current bounding box.center)]
|
482
|
956 |
\node[state,initial] (Q_0) {$0$};
|
490
|
957 |
\node[state] (Q_1) [below=of Q_0] {$1$};
|
|
958 |
\node[state, accepting] (Q_2) [below=of Q_1] {$2$};
|
|
959 |
|
|
960 |
\path[->] (Q_0) edge node [right] {$b$} (Q_1);
|
|
961 |
\path[->] (Q_1) edge node [right] {$a,b$} (Q_2);
|
|
962 |
\path[->] (Q_0) edge [loop above] node {$a, b$} ();
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
963 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
964 |
&
|
490
|
965 |
\begin{tabular}{r|ll}
|
|
966 |
states & $a$ & $b$\\
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
967 |
\hline
|
344
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
968 |
$\{\}\phantom{\star}$ & $\{\}$ & $\{\}$\\
|
490
|
969 |
start: $\{0\}\phantom{\star}$ & $\{0\}$ & $\{0,1\}$\\
|
|
970 |
$\{1\}\phantom{\star}$ & $\{2\}$ & $\{2\}$\\
|
|
971 |
$\{2\}\star$ & $\{\}$ & $\{\}$\\
|
|
972 |
$\{0,1\}\phantom{\star}$ & $\{0,2\}$ & $\{0,1,2\}$\\
|
|
973 |
$\{0,2\}\star$ & $\{0\}$ & $\{0,1\}$\\
|
|
974 |
$\{1,2\}\star$ & $\{2\}$ & $\{2\}$\\
|
|
975 |
$\{0,1,2\}\star$ & $\{0,2\}$ & $\{0,1,2\}$\\
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
976 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
977 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
978 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
979 |
|
490
|
980 |
\noindent The states of the corresponding DFA are given by generating
|
491
|
981 |
all subsets of the set $\{0,1,2\}$ (seen in the states column
|
490
|
982 |
in the table on the right). The other columns define the transition
|
491
|
983 |
function for the DFA for inputs $a$ and $b$. The first row states that
|
490
|
984 |
$\{\}$ is the sink state which has transitions for $a$ and $b$ to
|
|
985 |
itself. The next three lines are calculated as follows:
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
986 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
987 |
\begin{itemize}
|
490
|
988 |
\item Suppose you calculate the entry for the $a$-transition for state
|
|
989 |
$\{0\}$. Look for all states in the NFA that can be reached by such
|
|
990 |
a transition from this state; this is only state $0$; therefore from
|
|
991 |
state $\{0\}$ we can go to state $\{0\}$ via an $a$-transition.
|
|
992 |
\item Do the same for the $b$-transition; you can reach states $0$ and
|
|
993 |
$1$ in the NFA; therefore in the DFA we can go from state $\{0\}$ to
|
|
994 |
state $\{0,1\}$ via an $b$-transition.
|
|
995 |
\item Continue with the states $\{1\}$ and $\{2\}$.
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
996 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
997 |
|
491
|
998 |
\noindent
|
|
999 |
Once you filled in the transitions for `simple' states $\{0\}$
|
|
1000 |
.. $\{2\}$, you only have to build the union for the compound states
|
|
1001 |
$\{0,1\}$, $\{0,2\}$ and so on. For example for $\{0,1\}$ you take the
|
|
1002 |
union of Line $\{0\}$ and Line $\{1\}$, which gives $\{0,2\}$ for $a$,
|
|
1003 |
and $\{0,1,2\}$ for $b$. And so on.
|
344
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1004 |
|
491
|
1005 |
The starting state of the DFA can be calculated from the starting
|
|
1006 |
states of the NFA, that is in this case $\{0\}$. But in general there
|
|
1007 |
can of course be many starting states in the NFA and you would take
|
|
1008 |
the corresponding subset as \emph{the} starting state of the DFA.
|
|
1009 |
|
|
1010 |
The accepting states in the DFA are given by all sets that contain a
|
667
|
1011 |
$2$, which is the only accepting state in this NFA. But again in
|
491
|
1012 |
general if the subset contains any accepting state from the NFA, then
|
|
1013 |
the corresponding state in the DFA is accepting as well. This
|
|
1014 |
completes the subset construction. The corresponding DFA for the NFA
|
|
1015 |
shown above is:
|
|
1016 |
|
|
1017 |
\begin{equation}
|
490
|
1018 |
\begin{tikzpicture}[scale=0.8,>=stealth',very thick,
|
344
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1019 |
every state/.style={minimum size=0pt,
|
491
|
1020 |
draw=blue!50,very thick,fill=blue!20},
|
|
1021 |
baseline=(current bounding box.center)]
|
490
|
1022 |
\node[state,initial] (q0) {$0$};
|
|
1023 |
\node[state] (q01) [right=of q0] {$0,1$};
|
|
1024 |
\node[state,accepting] (q02) [below=of q01] {$0,2$};
|
|
1025 |
\node[state,accepting] (q012) [right=of q02] {$0,1,2$};
|
|
1026 |
\node[state] (q1) [below=0.5cm of q0] {$1$};
|
|
1027 |
\node[state,accepting] (q2) [below=1cm of q1] {$2$};
|
|
1028 |
\node[state] (qn) [below left=1cm of q2] {$\{\}$};
|
|
1029 |
\node[state,accepting] (q12) [below right=1cm of q2] {$1,2$};
|
|
1030 |
|
|
1031 |
\path[->] (q0) edge node [above] {$b$} (q01);
|
|
1032 |
\path[->] (q01) edge node [above] {$b$} (q012);
|
|
1033 |
\path[->] (q0) edge [loop above] node {$a$} ();
|
|
1034 |
\path[->] (q012) edge [loop right] node {$b$} ();
|
|
1035 |
\path[->] (q012) edge node [below] {$a$} (q02);
|
|
1036 |
\path[->] (q02) edge node [below] {$a$} (q0);
|
|
1037 |
\path[->] (q01) edge [bend left] node [left] {$a$} (q02);
|
|
1038 |
\path[->] (q02) edge [bend left] node [right] {$b$} (q01);
|
|
1039 |
\path[->] (q1) edge node [left] {$a,b$} (q2);
|
|
1040 |
\path[->] (q12) edge node [right] {$a, b$} (q2);
|
|
1041 |
\path[->] (q2) edge node [right] {$a, b$} (qn);
|
|
1042 |
\path[->] (qn) edge [loop left] node {$a,b$} ();
|
491
|
1043 |
\end{tikzpicture}\label{subsetdfa}
|
|
1044 |
\end{equation}
|
490
|
1045 |
|
|
1046 |
\noindent
|
|
1047 |
Please check that this is indeed a DFA. The big question is whether
|
491
|
1048 |
this DFA can recognise the same language as the NFA we started with?
|
490
|
1049 |
I let you ponder about this question.
|
|
1050 |
|
|
1051 |
|
491
|
1052 |
There are also two points to note: One is that very often in the
|
|
1053 |
subset construction the resulting DFA contains a number of ``dead''
|
|
1054 |
states that are never reachable from the starting state. This is
|
|
1055 |
obvious in the example, where state $\{1\}$, $\{2\}$, $\{1,2\}$ and
|
|
1056 |
$\{\}$ can never be reached from the starting state. But this might
|
|
1057 |
not always be as obvious as that. In effect the DFA in this example is
|
|
1058 |
not a \emph{minimal} DFA (more about this in a minute). Such dead
|
|
1059 |
states can be safely removed without changing the language that is
|
|
1060 |
recognised by the DFA. Another point is that in some cases, however,
|
|
1061 |
the subset construction produces a DFA that does \emph{not} contain
|
|
1062 |
any dead states\ldots{}this means it calculates a minimal DFA. Which
|
|
1063 |
in turn means that in some cases the number of states can by going
|
|
1064 |
from NFAs to DFAs exponentially increase, namely by $2^n$ (which is
|
|
1065 |
the number of subsets you can form for sets of $n$ states). This blow
|
|
1066 |
up in the number of states in the DFA is again bad news for how
|
|
1067 |
quickly you can decide whether a string is accepted by a DFA or
|
|
1068 |
not. So the caveat with DFAs is that they might make the task of
|
667
|
1069 |
finding the next state trivial, but might require $2^n$ times as many
|
874
|
1070 |
states than a NFA.\bigskip
|
490
|
1071 |
|
491
|
1072 |
\noindent
|
|
1073 |
To conclude this section, how conveniently we can
|
|
1074 |
implement the subset construction with our versions of NFAs and
|
698
|
1075 |
DFAs? Very conveniently. The code is just:
|
490
|
1076 |
|
|
1077 |
{\small\begin{lstlisting}[language=Scala]
|
|
1078 |
def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {
|
|
1079 |
DFA(nfa.starts,
|
|
1080 |
{ case (qs, c) => nfa.nexts(qs, c) },
|
|
1081 |
_.exists(nfa.fins))
|
|
1082 |
}
|
|
1083 |
\end{lstlisting}}
|
|
1084 |
|
491
|
1085 |
\noindent
|
|
1086 |
The interesting point in this code is that the state type of the
|
|
1087 |
calculated DFA is \texttt{Set[A]}. Think carefully that this works out
|
|
1088 |
correctly.
|
490
|
1089 |
|
491
|
1090 |
The DFA is then given by three components: the starting states, the
|
|
1091 |
transition function and the accepting-states function. The starting
|
|
1092 |
states are a set in the given NFA, but a single state in the DFA. The
|
|
1093 |
transition function, given the state \texttt{qs} and input \texttt{c},
|
|
1094 |
needs to produce the next state: this is the set of all NFA states
|
|
1095 |
that are reachable from each state in \texttt{qs}. The function
|
|
1096 |
\texttt{nexts} from the NFA class already calculates this for us. The
|
667
|
1097 |
accepting-states function for the DFA is true whenever at least one
|
491
|
1098 |
state in the subset is accepting (that is true) in the NFA.\medskip
|
|
1099 |
|
|
1100 |
\noindent
|
495
|
1101 |
You might be able to spend some quality time tinkering with this code
|
|
1102 |
and time to ponder about it. Then you will probably notice that it is
|
|
1103 |
actually a bit silly. The whole point of translating the NFA into a
|
|
1104 |
DFA via the subset construction is to make the decision of whether a
|
|
1105 |
string is accepted or not faster. Given the code above, the generated
|
|
1106 |
DFA will be exactly as fast, or as slow, as the NFA we started with
|
|
1107 |
(actually it will even be a tiny bit slower). The reason is that we
|
|
1108 |
just re-use the \texttt{nexts} function from the NFA. This function
|
|
1109 |
implements the non-deterministic breadth-first search. You might be
|
|
1110 |
thinking: This is cheating! \ldots{} Well, not quite as you will see
|
|
1111 |
later, but in terms of speed we still need to work a bit in order to
|
|
1112 |
get sometimes(!) a faster DFA. Let's do this next.
|
490
|
1113 |
|
|
1114 |
\subsection*{DFA Minimisation}
|
|
1115 |
|
491
|
1116 |
As seen in \eqref{subsetdfa}, the subset construction from NFA to a
|
|
1117 |
DFA can result in a rather ``inefficient'' DFA. Meaning there are
|
|
1118 |
states that are not needed. There are two kinds of such unneeded
|
495
|
1119 |
states: \emph{unreachable} states and \emph{non-distinguishable}
|
491
|
1120 |
states. The first kind of states can just be removed without affecting
|
|
1121 |
the language that can be recognised (after all they are
|
|
1122 |
unreachable). The second kind can also be recognised and thus a DFA
|
|
1123 |
can be \emph{minimised} by the following algorithm:
|
490
|
1124 |
|
|
1125 |
\begin{enumerate}
|
|
1126 |
\item Take all pairs $(q, p)$ with $q \not= p$
|
|
1127 |
\item Mark all pairs that accepting and non-accepting states
|
|
1128 |
\item For all unmarked pairs $(q, p)$ and all characters $c$
|
|
1129 |
test whether
|
|
1130 |
|
|
1131 |
\begin{center}
|
|
1132 |
$(\delta(q, c), \delta(p,c))$
|
|
1133 |
\end{center}
|
|
1134 |
|
|
1135 |
are marked. If there is one, then also mark $(q, p)$.
|
|
1136 |
\item Repeat last step until no change.
|
|
1137 |
\item All unmarked pairs can be merged.
|
|
1138 |
\end{enumerate}
|
|
1139 |
|
491
|
1140 |
\noindent Unfortunately, once we throw away all unreachable states in
|
|
1141 |
\eqref{subsetdfa}, all remaining states are needed. In order to
|
|
1142 |
illustrate the minimisation algorithm, consider the following DFA.
|
344
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1143 |
|
490
|
1144 |
\begin{center}
|
|
1145 |
\begin{tikzpicture}[>=stealth',very thick,auto,
|
|
1146 |
every state/.style={minimum size=0pt,
|
|
1147 |
inner sep=2pt,draw=blue!50,very thick,
|
|
1148 |
fill=blue!20}]
|
|
1149 |
\node[state,initial] (Q_0) {$Q_0$};
|
|
1150 |
\node[state] (Q_1) [right=of Q_0] {$Q_1$};
|
|
1151 |
\node[state] (Q_2) [below right=of Q_0] {$Q_2$};
|
|
1152 |
\node[state] (Q_3) [right=of Q_2] {$Q_3$};
|
|
1153 |
\node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$};
|
|
1154 |
\path[->] (Q_0) edge node [above] {$a$} (Q_1);
|
|
1155 |
\path[->] (Q_1) edge node [above] {$a$} (Q_4);
|
|
1156 |
\path[->] (Q_4) edge [loop right] node {$a, b$} ();
|
|
1157 |
\path[->] (Q_3) edge node [right] {$a$} (Q_4);
|
|
1158 |
\path[->] (Q_2) edge node [above] {$a$} (Q_3);
|
|
1159 |
\path[->] (Q_1) edge node [right] {$b$} (Q_2);
|
|
1160 |
\path[->] (Q_0) edge node [above] {$b$} (Q_2);
|
|
1161 |
\path[->] (Q_2) edge [loop left] node {$b$} ();
|
|
1162 |
\path[->] (Q_3) edge [bend left=95, looseness=1.3] node
|
|
1163 |
[below] {$b$} (Q_0);
|
|
1164 |
\end{tikzpicture}
|
|
1165 |
\end{center}
|
|
1166 |
|
|
1167 |
\noindent In Step 1 and 2 we consider essentially a triangle
|
|
1168 |
of the form
|
|
1169 |
|
|
1170 |
\begin{center}
|
|
1171 |
\begin{tikzpicture}[scale=0.6,line width=0.8mm]
|
|
1172 |
\draw (0,0) -- (4,0);
|
|
1173 |
\draw (0,1) -- (4,1);
|
|
1174 |
\draw (0,2) -- (3,2);
|
|
1175 |
\draw (0,3) -- (2,3);
|
|
1176 |
\draw (0,4) -- (1,4);
|
|
1177 |
|
|
1178 |
\draw (0,0) -- (0, 4);
|
|
1179 |
\draw (1,0) -- (1, 4);
|
|
1180 |
\draw (2,0) -- (2, 3);
|
|
1181 |
\draw (3,0) -- (3, 2);
|
|
1182 |
\draw (4,0) -- (4, 1);
|
|
1183 |
|
|
1184 |
\draw (0.5,-0.5) node {$Q_0$};
|
|
1185 |
\draw (1.5,-0.5) node {$Q_1$};
|
|
1186 |
\draw (2.5,-0.5) node {$Q_2$};
|
|
1187 |
\draw (3.5,-0.5) node {$Q_3$};
|
|
1188 |
|
|
1189 |
\draw (-0.5, 3.5) node {$Q_1$};
|
|
1190 |
\draw (-0.5, 2.5) node {$Q_2$};
|
|
1191 |
\draw (-0.5, 1.5) node {$Q_3$};
|
|
1192 |
\draw (-0.5, 0.5) node {$Q_4$};
|
|
1193 |
|
|
1194 |
\draw (0.5,0.5) node {\large$\star$};
|
|
1195 |
\draw (1.5,0.5) node {\large$\star$};
|
|
1196 |
\draw (2.5,0.5) node {\large$\star$};
|
|
1197 |
\draw (3.5,0.5) node {\large$\star$};
|
|
1198 |
\end{tikzpicture}
|
|
1199 |
\end{center}
|
|
1200 |
|
|
1201 |
\noindent where the lower row is filled with stars, because in
|
|
1202 |
the corresponding pairs there is always one state that is
|
|
1203 |
accepting ($Q_4$) and a state that is non-accepting (the other
|
|
1204 |
states).
|
|
1205 |
|
491
|
1206 |
In Step 3 we need to fill in more stars according whether
|
490
|
1207 |
one of the next-state pairs are marked. We have to do this
|
753
|
1208 |
for every unmarked field until there is no change any more.
|
490
|
1209 |
This gives the triangle
|
|
1210 |
|
|
1211 |
\begin{center}
|
|
1212 |
\begin{tikzpicture}[scale=0.6,line width=0.8mm]
|
|
1213 |
\draw (0,0) -- (4,0);
|
|
1214 |
\draw (0,1) -- (4,1);
|
|
1215 |
\draw (0,2) -- (3,2);
|
|
1216 |
\draw (0,3) -- (2,3);
|
|
1217 |
\draw (0,4) -- (1,4);
|
|
1218 |
|
|
1219 |
\draw (0,0) -- (0, 4);
|
|
1220 |
\draw (1,0) -- (1, 4);
|
|
1221 |
\draw (2,0) -- (2, 3);
|
|
1222 |
\draw (3,0) -- (3, 2);
|
|
1223 |
\draw (4,0) -- (4, 1);
|
|
1224 |
|
|
1225 |
\draw (0.5,-0.5) node {$Q_0$};
|
|
1226 |
\draw (1.5,-0.5) node {$Q_1$};
|
|
1227 |
\draw (2.5,-0.5) node {$Q_2$};
|
|
1228 |
\draw (3.5,-0.5) node {$Q_3$};
|
|
1229 |
|
|
1230 |
\draw (-0.5, 3.5) node {$Q_1$};
|
|
1231 |
\draw (-0.5, 2.5) node {$Q_2$};
|
|
1232 |
\draw (-0.5, 1.5) node {$Q_3$};
|
|
1233 |
\draw (-0.5, 0.5) node {$Q_4$};
|
|
1234 |
|
|
1235 |
\draw (0.5,0.5) node {\large$\star$};
|
|
1236 |
\draw (1.5,0.5) node {\large$\star$};
|
|
1237 |
\draw (2.5,0.5) node {\large$\star$};
|
|
1238 |
\draw (3.5,0.5) node {\large$\star$};
|
|
1239 |
\draw (0.5,1.5) node {\large$\star$};
|
|
1240 |
\draw (2.5,1.5) node {\large$\star$};
|
|
1241 |
\draw (0.5,3.5) node {\large$\star$};
|
|
1242 |
\draw (1.5,2.5) node {\large$\star$};
|
|
1243 |
\end{tikzpicture}
|
|
1244 |
\end{center}
|
|
1245 |
|
|
1246 |
\noindent which means states $Q_0$ and $Q_2$, as well as $Q_1$
|
|
1247 |
and $Q_3$ can be merged. This gives the following minimal DFA
|
|
1248 |
|
|
1249 |
\begin{center}
|
|
1250 |
\begin{tikzpicture}[>=stealth',very thick,auto,
|
|
1251 |
every state/.style={minimum size=0pt,
|
|
1252 |
inner sep=2pt,draw=blue!50,very thick,
|
|
1253 |
fill=blue!20}]
|
|
1254 |
\node[state,initial] (Q_02) {$Q_{0, 2}$};
|
|
1255 |
\node[state] (Q_13) [right=of Q_02] {$Q_{1, 3}$};
|
|
1256 |
\node[state, accepting] (Q_4) [right=of Q_13]
|
|
1257 |
{$Q_{4\phantom{,0}}$};
|
|
1258 |
\path[->] (Q_02) edge [bend left] node [above] {$a$} (Q_13);
|
|
1259 |
\path[->] (Q_13) edge [bend left] node [below] {$b$} (Q_02);
|
|
1260 |
\path[->] (Q_02) edge [loop below] node {$b$} ();
|
|
1261 |
\path[->] (Q_13) edge node [above] {$a$} (Q_4);
|
|
1262 |
\path[->] (Q_4) edge [loop above] node {$a, b$} ();
|
344
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1263 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1264 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1265 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1266 |
|
753
|
1267 |
\noindent This minimised DFA is certainly fast when it comes deciding
|
|
1268 |
whether a string is accepted or not. But this is not universally the
|
|
1269 |
case. Suppose you count the nodes in a regular expression (when
|
|
1270 |
represented as tree). If you look carefully at the Thompson
|
|
1271 |
Construction you can see that the constructed NFA has states that grow
|
|
1272 |
linearly in terms of the size of the regular expression. This is good,
|
|
1273 |
but as we have seen earlier deciding whether a string is matched by an
|
|
1274 |
NFA is hard. Translating an NFA into a DFA means deciding whether a
|
|
1275 |
string is matched by a DFA is easy, but the number of states can grow
|
|
1276 |
exponentially, even after minimisation. Say a NFA has $n$ states, then
|
|
1277 |
in the worst case the corresponding minimal DFA that can match the
|
|
1278 |
same language as the NFA might contain $2^n$ of states. Unfortunately
|
|
1279 |
in many interesting cases this worst case bound is the dominant
|
|
1280 |
factor.
|
|
1281 |
|
|
1282 |
|
492
|
1283 |
By the way, we are not bothering with implementing the above
|
667
|
1284 |
minimisation algorithm: while up to now all the transformations used
|
492
|
1285 |
some clever composition of functions, the minimisation algorithm
|
|
1286 |
cannot be implemented by just composing some functions. For this we
|
|
1287 |
would require a more concrete representation of the transition
|
|
1288 |
function (like maps). If we did this, however, then many advantages of
|
|
1289 |
the functions would be thrown away. So the compromise is to not being
|
753
|
1290 |
able to minimise (easily) our DFAs. We want to use regular expressions
|
|
1291 |
directly anyway.
|
492
|
1292 |
|
490
|
1293 |
\subsection*{Brzozowski's Method}
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1294 |
|
495
|
1295 |
I know this handout is already a long, long rant: but after all it is
|
|
1296 |
a topic that has been researched for more than 60 years. If you
|
|
1297 |
reflect on what you have read so far, the story is that you can take a
|
|
1298 |
regular expression, translate it via the Thompson Construction into an
|
491
|
1299 |
$\epsilon$NFA, then translate it into a NFA by removing all
|
|
1300 |
$\epsilon$-transitions, and then via the subset construction obtain a
|
|
1301 |
DFA. In all steps we made sure the language, or which strings can be
|
698
|
1302 |
recognised, stays the same. Of cause we should have proved this in
|
495
|
1303 |
each step, but let us cut corners here. After the last section, we
|
|
1304 |
can even minimise the DFA (maybe not in code). But again we made sure
|
|
1305 |
the same language is recognised. You might be wondering: Can we go
|
|
1306 |
into the other direction? Can we go from a DFA and obtain a regular
|
|
1307 |
expression that can recognise the same language as the DFA?\medskip
|
491
|
1308 |
|
|
1309 |
\noindent
|
|
1310 |
The answer is yes. Again there are several methods for calculating a
|
|
1311 |
regular expression for a DFA. I will show you Brzozowski's method
|
|
1312 |
because it calculates a regular expression using quite familiar
|
|
1313 |
transformations for solving equational systems. Consider the DFA:
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1314 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1315 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1316 |
\begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1317 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1318 |
inner sep=2pt,draw=blue!50,very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1319 |
fill=blue!20}]
|
482
|
1320 |
\node[state, initial] (q0) at ( 0,1) {$Q_0$};
|
|
1321 |
\node[state] (q1) at ( 1,1) {$Q_1$};
|
|
1322 |
\node[state, accepting] (q2) at ( 2,1) {$Q_2$};
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1323 |
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1324 |
(q1) edge[bend left] node[above] {$b$} (q0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1325 |
(q2) edge[bend left=50] node[below] {$b$} (q0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1326 |
(q1) edge node[above] {$a$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1327 |
(q2) edge [loop right] node {$a$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1328 |
(q0) edge [loop below] node {$b$} ();
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1329 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1330 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1331 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1332 |
\noindent for which we can set up the following equational
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1333 |
system
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1334 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1335 |
\begin{eqnarray}
|
482
|
1336 |
Q_0 & = & \ONE + Q_0\,b + Q_1\,b + Q_2\,b\\
|
|
1337 |
Q_1 & = & Q_0\,a\\
|
|
1338 |
Q_2 & = & Q_1\,a + Q_2\,a
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1339 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1340 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1341 |
\noindent There is an equation for each node in the DFA. Let
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1342 |
us have a look how the right-hand sides of the equations are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1343 |
constructed. First have a look at the second equation: the
|
482
|
1344 |
left-hand side is $Q_1$ and the right-hand side $Q_0\,a$. The
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1345 |
right-hand side is essentially all possible ways how to end up
|
482
|
1346 |
in node $Q_1$. There is only one incoming edge from $Q_0$ consuming
|
322
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1347 |
an $a$. Therefore the right hand side is this
|
482
|
1348 |
state followed by character---in this case $Q_0\,a$. Now lets
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1349 |
have a look at the third equation: there are two incoming
|
482
|
1350 |
edges for $Q_2$. Therefore we have two terms, namely $Q_1\,a$ and
|
|
1351 |
$Q_2\,a$. These terms are separated by $+$. The first states
|
|
1352 |
that if in state $Q_1$ consuming an $a$ will bring you to
|
485
|
1353 |
$Q_2$, and the second that being in $Q_2$ and consuming an $a$
|
482
|
1354 |
will make you stay in $Q_2$. The right-hand side of the
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1355 |
first equation is constructed similarly: there are three
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1356 |
incoming edges, therefore there are three terms. There is
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1357 |
one exception in that we also ``add'' $\ONE$ to the
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1358 |
first equation, because it corresponds to the starting state
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1359 |
in the DFA.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1360 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1361 |
Having constructed the equational system, the question is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1362 |
how to solve it? Remarkably the rules are very similar to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1363 |
solving usual linear equational systems. For example the
|
482
|
1364 |
second equation does not contain the variable $Q_1$ on the
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1365 |
right-hand side of the equation. We can therefore eliminate
|
482
|
1366 |
$Q_1$ from the system by just substituting this equation
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1367 |
into the other two. This gives
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1368 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1369 |
\begin{eqnarray}
|
482
|
1370 |
Q_0 & = & \ONE + Q_0\,b + Q_0\,a\,b + Q_2\,b\\
|
|
1371 |
Q_2 & = & Q_0\,a\,a + Q_2\,a
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1372 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1373 |
|
698
|
1374 |
\noindent where in Equation (6) we have two occurrences
|
482
|
1375 |
of $Q_0$. Like the laws about $+$ and $\cdot$, we can simplify
|
698
|
1376 |
Equation (6) to obtain the following two equations:
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1377 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1378 |
\begin{eqnarray}
|
482
|
1379 |
Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\
|
|
1380 |
Q_2 & = & Q_0\,a\,a + Q_2\,a
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1381 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1382 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1383 |
\noindent Unfortunately we cannot make any more progress with
|
578
|
1384 |
substituting equations, because both (8) and (9) contain the
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1385 |
variable on the left-hand side also on the right-hand side.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1386 |
Here we need to now use a law that is different from the usual
|
349
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1387 |
laws about linear equations. It is called \emph{Arden's rule}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1388 |
It states that if an equation is of the form $q = q\,r + s$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1389 |
then it can be transformed to $q = s\, r^*$. Since we can
|
578
|
1390 |
assume $+$ is symmetric, Equation (9) is of that form: $s$ is
|
482
|
1391 |
$Q_0\,a\,a$ and $r$ is $a$. That means we can transform
|
578
|
1392 |
(9) to obtain the two new equations
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1393 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1394 |
\begin{eqnarray}
|
482
|
1395 |
Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\
|
|
1396 |
Q_2 & = & Q_0\,a\,a\,(a^*)
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1397 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1398 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1399 |
\noindent Now again we can substitute the second equation into
|
482
|
1400 |
the first in order to eliminate the variable $Q_2$.
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1401 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1402 |
\begin{eqnarray}
|
482
|
1403 |
Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_0\,a\,a\,(a^*)\,b
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1404 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1405 |
|
482
|
1406 |
\noindent Pulling $Q_0$ out as a single factor gives:
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1407 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1408 |
\begin{eqnarray}
|
482
|
1409 |
Q_0 & = & \ONE + Q_0\,(b + a\,b + a\,a\,(a^*)\,b)
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1410 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1411 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1412 |
\noindent This equation is again of the form so that we can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1413 |
apply Arden's rule ($r$ is $b + a\,b + a\,a\,(a^*)\,b$ and $s$
|
482
|
1414 |
is $\ONE$). This gives as solution for $Q_0$ the following
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1415 |
regular expression:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1416 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1417 |
\begin{eqnarray}
|
482
|
1418 |
Q_0 & = & \ONE\,(b + a\,b + a\,a\,(a^*)\,b)^*
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1419 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1420 |
|
349
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1421 |
\noindent Since this is a regular expression, we can simplify
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1422 |
away the $\ONE$ to obtain the slightly simpler regular
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1423 |
expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1424 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1425 |
\begin{eqnarray}
|
482
|
1426 |
Q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1427 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1428 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1429 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1430 |
Now we can unwind this process and obtain the solutions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1431 |
for the other equations. This gives:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1432 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1433 |
\begin{eqnarray}
|
482
|
1434 |
Q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\\
|
|
1435 |
Q_1 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\\
|
|
1436 |
Q_2 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^*
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1437 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1438 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1439 |
\noindent Finally, we only need to ``add'' up the equations
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1440 |
which correspond to a terminal state. In our running example,
|
482
|
1441 |
this is just $Q_2$. Consequently, a regular expression
|
491
|
1442 |
that recognises the same language as the DFA is
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1443 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1444 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1445 |
(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^*
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1446 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1447 |
|
491
|
1448 |
\noindent You can somewhat crosscheck your solution by taking a string
|
|
1449 |
the regular expression can match and and see whether it can be matched
|
|
1450 |
by the DFA. One string for example is $aaa$ and \emph{voila} this
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1451 |
string is also matched by the automaton.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1452 |
|
491
|
1453 |
We should prove that Brzozowski's method really produces an equivalent
|
|
1454 |
regular expression. But for the purposes of this module, we omit
|
|
1455 |
this. I guess you are relieved.
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1456 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1457 |
|
490
|
1458 |
\subsection*{Regular Languages}
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1459 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1460 |
Given the constructions in the previous sections we obtain
|
349
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1461 |
the following overall picture:
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1462 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1463 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1464 |
\begin{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1465 |
\node (rexp) {\bf Regexps};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1466 |
\node (nfa) [right=of rexp] {\bf NFAs};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1467 |
\node (dfa) [right=of nfa] {\bf DFAs};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1468 |
\node (mdfa) [right=of dfa] {\bf\begin{tabular}{c}minimal\\ DFAs\end{tabular}};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1469 |
\path[->,line width=1mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1470 |
\path[->,line width=1mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1471 |
\path[->,line width=1mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);
|
344
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1472 |
\path[->,line width=1mm] (dfa) edge [bend left=45] node [below] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp);
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1473 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1474 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1475 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1476 |
\noindent By going from regular expressions over NFAs to DFAs,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1477 |
we can always ensure that for every regular expression there
|
349
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1478 |
exists a NFA and a DFA that can recognise the same language.
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1479 |
Although we did not prove this fact. Similarly by going from
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1480 |
DFAs to regular expressions, we can make sure for every DFA
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1481 |
there exists a regular expression that can recognise the same
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1482 |
language. Again we did not prove this fact.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1483 |
|
491
|
1484 |
The fundamental conclusion we can draw is that automata and regular
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1485 |
expressions can recognise the same set of languages:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1486 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1487 |
\begin{quote} A language is \emph{regular} iff there exists a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1488 |
regular expression that recognises all its strings.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1489 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1490 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1491 |
\noindent or equivalently
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1492 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1493 |
\begin{quote} A language is \emph{regular} iff there exists an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1494 |
automaton that recognises all its strings.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1495 |
\end{quote}
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1496 |
|
698
|
1497 |
\noindent Note that this is not a statement for a particular language
|
491
|
1498 |
(that is a particular set of strings), but about a large class of
|
|
1499 |
languages, namely the regular ones.
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1500 |
|
491
|
1501 |
As a consequence for deciding whether a string is recognised by a
|
|
1502 |
regular expression, we could use our algorithm based on derivatives or
|
|
1503 |
NFAs or DFAs. But let us quickly look at what the differences mean in
|
|
1504 |
computational terms. Translating a regular expression into a NFA gives
|
|
1505 |
us an automaton that has $O(n)$ states---that means the size of the
|
|
1506 |
NFA grows linearly with the size of the regular expression. The
|
|
1507 |
problem with NFAs is that the problem of deciding whether a string is
|
|
1508 |
accepted or not is computationally not cheap. Remember with NFAs we
|
|
1509 |
have potentially many next states even for the same input and also
|
|
1510 |
have the silent $\epsilon$-transitions. If we want to find a path from
|
|
1511 |
the starting state of a NFA to an accepting state, we need to consider
|
|
1512 |
all possibilities. In Ruby, Python and Java this is done by a
|
|
1513 |
depth-first search, which in turn means that if a ``wrong'' choice is
|
|
1514 |
made, the algorithm has to backtrack and thus explore all potential
|
|
1515 |
candidates. This is exactly the reason why Ruby, Python and Java are
|
|
1516 |
so slow for evil regular expressions. An alternative to the
|
|
1517 |
potentially slow depth-first search is to explore the search space in
|
|
1518 |
a breadth-first fashion, but this might incur a big memory penalty.
|
|
1519 |
|
|
1520 |
To avoid the problems with NFAs, we can translate them into DFAs. With
|
|
1521 |
DFAs the problem of deciding whether a string is recognised or not is
|
|
1522 |
much simpler, because in each state it is completely determined what
|
|
1523 |
the next state will be for a given input. So no search is needed. The
|
|
1524 |
problem with this is that the translation to DFAs can explode
|
|
1525 |
exponentially the number of states. Therefore when this route is
|
|
1526 |
taken, we definitely need to minimise the resulting DFAs in order to
|
|
1527 |
have an acceptable memory and runtime behaviour. But remember the
|
|
1528 |
subset construction in the worst case explodes the number of states by
|
|
1529 |
$2^n$. Effectively also the translation to DFAs can incur a big
|
349
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1530 |
runtime penalty.
|
269
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1531 |
|
491
|
1532 |
But this does not mean that everything is bad with automata. Recall
|
|
1533 |
the problem of finding a regular expressions for the language that is
|
|
1534 |
\emph{not} recognised by a regular expression. In our implementation
|
|
1535 |
we added explicitly such a regular expressions because they are useful
|
|
1536 |
for recognising comments. But in principle we did not need to. The
|
|
1537 |
argument for this is as follows: take a regular expression, translate
|
349
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1538 |
it into a NFA and then a DFA that both recognise the same
|
491
|
1539 |
language. Once you have the DFA it is very easy to construct the
|
|
1540 |
automaton for the language not recognised by a DFA. If the DFA is
|
|
1541 |
completed (this is important!), then you just need to exchange the
|
|
1542 |
accepting and non-accepting states. You can then translate this DFA
|
|
1543 |
back into a regular expression and that will be the regular expression
|
|
1544 |
that can match all strings the original regular expression could
|
|
1545 |
\emph{not} match.
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1546 |
|
491
|
1547 |
It is also interesting that not all languages are regular. The most
|
|
1548 |
well-known example of a language that is not regular consists of all
|
|
1549 |
the strings of the form
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1550 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1551 |
\[a^n\,b^n\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1552 |
|
491
|
1553 |
\noindent meaning strings that have the same number of $a$s and
|
|
1554 |
$b$s. You can try, but you cannot find a regular expression for this
|
|
1555 |
language and also not an automaton. One can actually prove that there
|
|
1556 |
is no regular expression nor automaton for this language, but again
|
|
1557 |
that would lead us too far afield for what we want to do in this
|
|
1558 |
module.
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1559 |
|
492
|
1560 |
|
|
1561 |
\subsection*{Where Have Derivatives Gone?}
|
|
1562 |
|
764
|
1563 |
%%Still to be done\bigskip
|
|
1564 |
|
|
1565 |
\noindent
|
|
1566 |
By now you are probably fed up with this text. It is now way too long
|
|
1567 |
for one lecture, but there is still one aspect of the
|
|
1568 |
automata-regular-expression-connection I like to describe:\medskip
|
518
|
1569 |
|
764
|
1570 |
\noindent
|
|
1571 |
Where have the derivatives gone? Did we just forget them? Well, they
|
|
1572 |
actually do play a role of generating a DFA from a regular expression.
|
|
1573 |
And we can also see this in our implementation\ldots{}because there is
|
|
1574 |
one flaw in our representation of automata and transitions as partial
|
874
|
1575 |
functions....remember I said something about fishy things.
|
|
1576 |
Namely, we can represent automata with infinite states, which is
|
764
|
1577 |
actually forbidden by the definition of what an automaton is. We can
|
|
1578 |
exploit this flaw as follows: Suppose our alphabet consists of the
|
|
1579 |
characters $c_1$ to $c_n$. Then we can generate an ``automaton''
|
|
1580 |
(it is not really one because it has infinite states) by taking
|
|
1581 |
as starting state the regular expression $r$ for which we
|
|
1582 |
want to generate an automaton. There are $n$ next-states which
|
|
1583 |
corresponds to the derivatives of $r$ according to $c_1$ to $c_n$.
|
|
1584 |
Implementing this in our slightly ``flawed'' representation is
|
|
1585 |
not too difficult. This will give a picture for the ``automaton''
|
|
1586 |
looking something like this, except that it extends infinitely
|
|
1587 |
far to the right:
|
|
1588 |
|
492
|
1589 |
|
764
|
1590 |
\begin{center}
|
|
1591 |
\begin{tikzpicture}
|
|
1592 |
[level distance=25mm,very thick,auto,
|
|
1593 |
level 1/.style={sibling distance=30mm},
|
|
1594 |
level 2/.style={sibling distance=15mm},
|
|
1595 |
every node/.style={minimum size=30pt,
|
|
1596 |
inner sep=0pt,circle,draw=blue!50,very thick,
|
|
1597 |
fill=blue!20}]
|
|
1598 |
\node {$r$} [grow=right]
|
|
1599 |
child[->] {node (cn) {$d_{c_n}$}
|
|
1600 |
child { node {$dd_{c_nc_n}$}}
|
|
1601 |
child { node {$dd_{c_nc_1}$}}
|
|
1602 |
%edge from parent node[left] {$c_n$}
|
|
1603 |
}
|
|
1604 |
child[->] {node (c1) {$d_{c_1}$}
|
|
1605 |
child { node {$dd_{c_1c_n}$}}
|
|
1606 |
child { node {$dd_{c_1c_1}$}}
|
|
1607 |
%edge from parent node[left] {$c_1$}
|
|
1608 |
};
|
|
1609 |
%%\draw (cn) -- (c1) node {\vdots};
|
|
1610 |
\end{tikzpicture}
|
|
1611 |
\end{center}
|
|
1612 |
|
|
1613 |
\noindent
|
|
1614 |
I let you implement this ``automaton''.
|
|
1615 |
|
|
1616 |
While this makes all sense (modulo the flaw with the infinite states),
|
874
|
1617 |
does this automaton teach us anything new? The answer is no, because it
|
764
|
1618 |
boils down to just another implementation of the Brzozowski
|
874
|
1619 |
algorithm from Lecture 2. There \emph{is} however something interesting
|
|
1620 |
in this construction
|
764
|
1621 |
which Brzozowski already cleverly found out, because there is
|
|
1622 |
a way to restrict the number of states to something finite.
|
874
|
1623 |
Meaning it would give us a real automaton.
|
764
|
1624 |
However, this would lead us far, far away from what we should
|
|
1625 |
discuss here.
|
|
1626 |
|
|
1627 |
|
492
|
1628 |
|
490
|
1629 |
%\section*{Further Reading}
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1630 |
|
490
|
1631 |
%Compare what a ``human expert'' would create as an automaton for the
|
|
1632 |
%regular expression $a\cdot (b + c)^*$ and what the Thomson
|
|
1633 |
%algorithm generates.
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1634 |
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1635 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1636 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1637 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1638 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1639 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1640 |
%%% End:
|
482
|
1641 |
|
|
1642 |
|