123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
251
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
217
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../langs}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../graphics}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
\usepackage{../data}
|
480
|
6 |
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
\begin{document}
|
571
|
9 |
\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
|
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
\section*{Handout 2 (Regular Expression Matching)}
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
|
412
|
14 |
This lecture is about implementing a more efficient regular expression
|
478
|
15 |
matcher (the plots on the right below)---more efficient than the
|
|
16 |
matchers from regular expression libraries in Ruby, Python and Java
|
492
|
17 |
(the plots on the left). The first pair of plots shows the running time
|
478
|
18 |
for the regular expression $(a^*)^*\cdot b$ and strings composed of
|
|
19 |
$n$ \pcode{a}s (meaning this regular expression actually does not
|
492
|
20 |
match the strings). The second pair of plots shows the running time for
|
478
|
21 |
the regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings
|
|
22 |
also composed of $n$ \pcode{a}s (this time the regular expressions
|
412
|
23 |
match the strings). To see the substantial differences in the left
|
478
|
24 |
and right plots below, note the different scales of the $x$-axes.
|
|
25 |
|
510
|
26 |
|
478
|
27 |
\begin{center}
|
|
28 |
Graphs: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$
|
|
29 |
\begin{tabular}{@{}cc@{}}
|
550
|
30 |
\begin{tikzpicture}[baseline=(current bounding box.north)]
|
|
31 |
\begin{axis}[
|
478
|
32 |
xlabel={$n$},
|
|
33 |
x label style={at={(1.05,0.0)}},
|
|
34 |
ylabel={time in secs},
|
|
35 |
enlargelimits=false,
|
|
36 |
xtick={0,5,...,30},
|
|
37 |
xmax=33,
|
|
38 |
ymax=35,
|
|
39 |
ytick={0,5,...,30},
|
|
40 |
scaled ticks=false,
|
|
41 |
axis lines=left,
|
|
42 |
width=5cm,
|
|
43 |
height=5cm,
|
550
|
44 |
legend entries={Java 8, Python},
|
478
|
45 |
legend pos=north west,
|
|
46 |
legend cell align=left]
|
|
47 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
|
|
48 |
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
|
|
49 |
\end{axis}
|
|
50 |
\end{tikzpicture}
|
|
51 |
&
|
550
|
52 |
\begin{tikzpicture}[baseline=(current bounding box.north)]
|
478
|
53 |
\begin{axis}[
|
|
54 |
xlabel={$n$},
|
488
|
55 |
x label style={at={(1.1,0.0)}},
|
|
56 |
%%xtick={0,1000000,...,5000000},
|
478
|
57 |
ylabel={time in secs},
|
|
58 |
enlargelimits=false,
|
|
59 |
ymax=35,
|
|
60 |
ytick={0,5,...,30},
|
|
61 |
axis lines=left,
|
488
|
62 |
%scaled ticks=false,
|
478
|
63 |
width=6.5cm,
|
|
64 |
height=5cm,
|
488
|
65 |
legend entries={Our matcher},
|
478
|
66 |
legend pos=north east,
|
|
67 |
legend cell align=left]
|
|
68 |
%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
|
|
69 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
|
|
70 |
\end{axis}
|
|
71 |
\end{tikzpicture}
|
|
72 |
\end{tabular}
|
488
|
73 |
\end{center}\bigskip
|
263
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
\begin{center}
|
415
|
76 |
Graphs: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$\\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
\begin{tabular}{@{}cc@{}}
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
\begin{tikzpicture}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
\begin{axis}[
|
414
|
80 |
xlabel={$n$},
|
|
81 |
x label style={at={(1.05,0.0)}},
|
412
|
82 |
ylabel={\small time in secs},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
enlargelimits=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
xtick={0,5,...,30},
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
xmax=33,
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
ymax=35,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
ytick={0,5,...,30},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
axis lines=left,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
width=5cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
height=5cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
legend entries={Python,Ruby},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
legend pos=north west,
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
legend cell align=left]
|
434
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
\end{axis}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
\end{tikzpicture}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
&
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
\begin{tikzpicture}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
\begin{axis}[
|
414
|
102 |
xlabel={$n$},
|
|
103 |
x label style={at={(1.1,0.05)}},
|
412
|
104 |
ylabel={\small time in secs},
|
|
105 |
enlargelimits=false,
|
477
|
106 |
xtick={0,2500,...,11000},
|
|
107 |
xmax=12000,
|
412
|
108 |
ymax=35,
|
|
109 |
ytick={0,5,...,30},
|
|
110 |
scaled ticks=false,
|
|
111 |
axis lines=left,
|
|
112 |
width=6.5cm,
|
478
|
113 |
height=5cm,
|
488
|
114 |
legend entries={Our matcher},
|
478
|
115 |
legend pos=north east,
|
|
116 |
legend cell align=left]
|
|
117 |
%\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
|
412
|
118 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
|
|
119 |
\end{axis}
|
|
120 |
\end{tikzpicture}
|
|
121 |
\end{tabular}
|
|
122 |
\end{center}
|
488
|
123 |
\bigskip
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
|
412
|
125 |
\noindent
|
488
|
126 |
In what follows we will use these regular expressions and strings as
|
|
127 |
running examples. There will be several versions (V1, V2, V3,\ldots)
|
|
128 |
of our matcher.\footnote{The corresponding files are
|
|
129 |
\texttt{re1.scala}, \texttt{re2.scala} and so on. As usual, you can
|
|
130 |
find the code on KEATS.}\bigskip
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
|
478
|
132 |
\noindent
|
412
|
133 |
Having specified in the previous lecture what
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
problem our regular expression matcher is supposed to solve,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
namely for any given regular expression $r$ and string $s$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
answer \textit{true} if and only if
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
139 |
s \in L(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
140 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
141 |
|
488
|
142 |
\noindent we can look for an algorithm to solve this problem. Clearly
|
412
|
143 |
we cannot use the function $L$ directly for this, because in general
|
|
144 |
the set of strings $L$ returns is infinite (recall what $L(a^*)$ is).
|
|
145 |
In such cases there is no way we can implement an exhaustive test for
|
|
146 |
whether a string is member of this set or not. In contrast our
|
|
147 |
matching algorithm will operate on the regular expression $r$ and
|
414
|
148 |
string $s$, only, which are both finite objects. Before we explain
|
412
|
149 |
the matching algorithm, however, let us have a closer look at what it
|
|
150 |
means when two regular expressions are equivalent.
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
\subsection*{Regular Expression Equivalences}
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
153 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
We already defined in Handout 1 what it means for two regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
expressions to be equivalent, namely if their meaning is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
same language:
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
r_1 \equiv r_2 \;\dn\; L(r_1) = L(r_2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
It is relatively easy to verify that some concrete equivalences
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
hold, for example
|
124
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
\begin{center}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
$(a + b) + c$ & $\equiv$ & $a + (b + c)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
$a + a$ & $\equiv$ & $a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
$a + b$ & $\equiv$ & $b + a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\\
|
124
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
\end{center}
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
175 |
|
124
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
\noindent
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
but also easy to verify that the following regular expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
are \emph{not} equivalent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
$a \cdot a$ & $\not\equiv$ & $a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
\noindent I leave it to you to verify these equivalences and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
non-equivalences. It is also interesting to look at some
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
corner cases involving $\ONE$ and $\ZERO$:
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
\begin{tabular}{rcl}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
$a + \ONE$ & $\not\equiv$ & $a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
$\ONE$ & $\equiv$ & $\ZERO^*$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
$\ONE^*$ & $\equiv$ & $\ONE$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
197 |
$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
198 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
199 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
200 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
201 |
\noindent Again I leave it to you to make sure you agree
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
202 |
with these equivalences and non-equivalences.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
203 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
204 |
|
318
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
205 |
For our matching algorithm however the following seven
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
206 |
equivalences will play an important role:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
207 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
208 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
209 |
\begin{tabular}{rcl}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
210 |
$r + \ZERO$ & $\equiv$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
211 |
$\ZERO + r$ & $\equiv$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
212 |
$r \cdot \ONE$ & $\equiv$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
$\ONE \cdot r$ & $\equiv$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
$r + r$ & $\equiv$ & $r$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
|
412
|
220 |
\noindent which always hold no matter what the regular expression $r$
|
|
221 |
looks like. The first two are easy to verify since $L(\ZERO)$ is the
|
|
222 |
empty set. The next two are also easy to verify since $L(\ONE) =
|
|
223 |
\{[]\}$ and appending the empty string to every string of another set,
|
|
224 |
leaves the set unchanged. Be careful to fully comprehend the fifth and
|
|
225 |
sixth equivalence: if you concatenate two sets of strings and one is
|
|
226 |
the empty set, then the concatenation will also be the empty set. To
|
|
227 |
see this, check the definition of $\_ @ \_$ for sets. The last
|
|
228 |
equivalence is again trivial.
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
What will be important later on is that we can orient these
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
equivalences and read them from left to right. In this way we
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
can view them as \emph{simplification rules}. Consider for
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
example the regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
\begin{equation}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
\label{big}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
\end{equation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
|
412
|
240 |
\noindent If we can find an equivalent regular expression that is
|
488
|
241 |
simpler (that usually means smaller), then this might potentially make
|
|
242 |
our matching algorithm run faster. We can look for such a simpler
|
|
243 |
regular expression $r'$ because whether a string $s$ is in $L(r)$ or
|
|
244 |
in $L(r')$ with $r\equiv r'$ will always give the same answer. Yes?
|
|
245 |
|
|
246 |
In the example above you will see that the regular expression is
|
|
247 |
equivalent to just $r_1$. You can verify this by iteratively applying
|
|
248 |
the simplification rules from above:
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
251 |
\begin{tabular}{ll}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
252 |
& $(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
253 |
(\underline{r_4 \cdot \ZERO})$\smallskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
254 |
$\equiv$ & $(r_1 + \ZERO) \cdot \ONE + \underline{((\ONE + r_2) + r_3) \cdot
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
255 |
\ZERO}$\smallskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
256 |
$\equiv$ & $\underline{(r_1 + \ZERO) \cdot \ONE} + \ZERO$\smallskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
257 |
$\equiv$ & $(\underline{r_1 + \ZERO}) + \ZERO$\smallskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
258 |
$\equiv$ & $\underline{r_1 + \ZERO}$\smallskip\\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
259 |
$\equiv$ & $r_1$\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
261 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
262 |
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
263 |
\noindent In each step, I underlined where a simplification
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
rule is applied. Our matching algorithm in the next section
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
265 |
will often generate such ``useless'' $\ONE$s and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
$\ZERO$s, therefore simplifying them away will make the
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
267 |
algorithm quite a bit faster.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
268 |
|
488
|
269 |
Finally here are three equivalences between regular expressions which are
|
479
|
270 |
not so obvious:
|
|
271 |
|
|
272 |
\begin{center}
|
|
273 |
\begin{tabular}{rcl}
|
|
274 |
$r^*$ & $\equiv$ & $1 + r\cdot r^*$\\
|
|
275 |
$(r_1 + r_2)^*$ & $\equiv$ & $r_1^* \cdot (r_2\cdot r_1^*)^*$\\
|
|
276 |
$(r_1 \cdot r_2)^*$ & $\equiv$ & $1 + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\
|
|
277 |
\end{tabular}
|
|
278 |
\end{center}
|
|
279 |
|
|
280 |
\noindent
|
566
|
281 |
We will not use them in our algorithm, but feel free to convince yourself
|
492
|
282 |
that they hold. As an aside, there has been a lot of research about
|
|
283 |
questions like: Can one always decide when two regular expressions are
|
488
|
284 |
equivalent or not? What does an algorithm look like to decide this
|
510
|
285 |
efficiently? So in general it is not a trivial problem.
|
479
|
286 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
287 |
\subsection*{The Matching Algorithm}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
288 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
289 |
The algorithm we will define below consists of two parts. One
|
412
|
290 |
is the function $\textit{nullable}$ which takes a regular expression as
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
291 |
argument and decides whether it can match the empty string
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
292 |
(this means it returns a boolean in Scala). This can be easily
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
293 |
defined recursively as follows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
294 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
295 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
296 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
412
|
297 |
$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\
|
|
298 |
$\textit{nullable}(\ONE)$ & $\dn$ & $\textit{true}$\\
|
|
299 |
$\textit{nullable}(c)$ & $\dn$ & $\textit{false}$\\
|
|
300 |
$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\
|
|
301 |
$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
|
|
302 |
$\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$ \\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
303 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
304 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
305 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
306 |
\noindent The idea behind this function is that the following
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
307 |
property holds:
|
124
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
\[
|
412
|
310 |
\textit{nullable}(r) \;\;\text{if and only if}\;\; []\in L(r)
|
124
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
312 |
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
313 |
\noindent Note on the left-hand side of the if-and-only-if we
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
314 |
have a function we can implement; on the right we have its
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
315 |
specification (which we cannot implement in a programming
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
316 |
language).
|
124
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
317 |
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
318 |
The other function of our matching algorithm calculates a
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
\emph{derivative} of a regular expression. This is a function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
320 |
which will take a regular expression, say $r$, and a
|
412
|
321 |
character, say $c$, as arguments and returns a new regular
|
488
|
322 |
expression. Be mindful that the intuition behind this function
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
323 |
is not so easy to grasp on first reading. Essentially this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
function solves the following problem: if $r$ can match a
|
488
|
325 |
string of the form $c\!::\!s$, what does a regular
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
326 |
expression look like that can match just $s$? The definition
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
of this function is as follows:
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
328 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
329 |
\begin{center}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
330 |
\begin{tabular}{l@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
|
414
|
331 |
$\textit{der}\, c\, (\ZERO)$ & $\dn$ & $\ZERO$\\
|
|
332 |
$\textit{der}\, c\, (\ONE)$ & $\dn$ & $\ZERO$ \\
|
|
333 |
$\textit{der}\, c\, (d)$ & $\dn$ & if $c = d$ then $\ONE$ else $\ZERO$\\
|
|
334 |
$\textit{der}\, c\, (r_1 + r_2)$ & $\dn$ & $\textit{der}\, c\, r_1 + \textit{der}\, c\, r_2$\\
|
|
335 |
$\textit{der}\, c\, (r_1 \cdot r_2)$ & $\dn$ & if $\textit{nullable} (r_1)$\\
|
|
336 |
& & then $(\textit{der}\,c\,r_1) \cdot r_2 + \textit{der}\, c\, r_2$\\
|
|
337 |
& & else $(\textit{der}\, c\, r_1) \cdot r_2$\\
|
|
338 |
$\textit{der}\, c\, (r^*)$ & $\dn$ & $(\textit{der}\,c\,r) \cdot (r^*)$
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
339 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
340 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
341 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
342 |
\noindent The first two clauses can be rationalised as
|
414
|
343 |
follows: recall that $\textit{der}$ should calculate a regular
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
344 |
expression so that given the ``input'' regular expression can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
345 |
match a string of the form $c\!::\!s$, we want a regular
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
346 |
expression for $s$. Since neither $\ZERO$ nor $\ONE$
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
347 |
can match a string of the form $c\!::\!s$, we return
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
348 |
$\ZERO$. In the third case we have to make a
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
349 |
case-distinction: In case the regular expression is $c$, then
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
350 |
clearly it can recognise a string of the form $c\!::\!s$, just
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
351 |
that $s$ is the empty string. Therefore we return the
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
352 |
$\ONE$-regular expression. In the other case we again
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
353 |
return $\ZERO$ since no string of the $c\!::\!s$ can be
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
354 |
matched. Next come the recursive cases, which are a bit more
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
355 |
involved. Fortunately, the $+$-case is still relatively
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
356 |
straightforward: all strings of the form $c\!::\!s$ are either
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
357 |
matched by the regular expression $r_1$ or $r_2$. So we just
|
414
|
358 |
have to recursively call $\textit{der}$ with these two regular
|
332
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
359 |
expressions and compose the results again with $+$. Makes
|
412
|
360 |
sense?
|
|
361 |
|
|
362 |
The $\cdot$-case is more complicated: if $r_1\cdot r_2$
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
363 |
matches a string of the form $c\!::\!s$, then the first part
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
364 |
must be matched by $r_1$. Consequently, it makes sense to
|
414
|
365 |
construct the regular expression for $s$ by calling $\textit{der}$ with
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
366 |
$r_1$ and ``appending'' $r_2$. There is however one exception
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
367 |
to this simple rule: if $r_1$ can match the empty string, then
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
368 |
all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
369 |
nullable (that is can match the empty string) we have to allow
|
414
|
370 |
the choice $\textit{der}\,c\,r_2$ for calculating the regular
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
371 |
expression that can match $s$. Therefore we have to add the
|
414
|
372 |
regular expression $\textit{der}\,c\,r_2$ in the result. The $*$-case
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
373 |
is again simple: if $r^*$ matches a string of the form
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
374 |
$c\!::\!s$, then the first part must be ``matched'' by a
|
414
|
375 |
single copy of $r$. Therefore we call recursively $\textit{der}\,c\,r$
|
|
376 |
and ``append'' $r^*$ in order to match the rest of $s$. Still
|
|
377 |
makes sense?
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
378 |
|
488
|
379 |
If all this did not make sense yet, here is another way to explain the
|
|
380 |
definition of $\textit{der}$ by considering the following operation on
|
|
381 |
sets:
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
382 |
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
383 |
\begin{equation}\label{Der}
|
414
|
384 |
\textit{Der}\,c\,A\;\dn\;\{s\,|\,c\!::\!s \in A\}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
385 |
\end{equation}
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
386 |
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
387 |
\noindent This operation essentially transforms a set of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
388 |
strings $A$ by filtering out all strings that do not start
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
389 |
with $c$ and then strips off the $c$ from all the remaining
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
390 |
strings. For example suppose $A = \{f\!oo, bar, f\!rak\}$ then
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
391 |
|
414
|
392 |
\[ \textit{Der}\,f\,A = \{oo, rak\}\quad,\quad
|
|
393 |
\textit{Der}\,b\,A = \{ar\} \quad \text{and} \quad
|
|
394 |
\textit{Der}\,a\,A = \{\}
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
395 |
\]
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
396 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
397 |
\noindent
|
414
|
398 |
Note that in the last case $\textit{Der}$ is empty, because no string in $A$
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
399 |
starts with $a$. With this operation we can state the following
|
414
|
400 |
property about $\textit{der}$:
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
401 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
402 |
\[
|
414
|
403 |
L(\textit{der}\,c\,r) = \textit{Der}\,c\,(L(r))
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
404 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
405 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
406 |
\noindent
|
414
|
407 |
This property clarifies what regular expression $\textit{der}$ calculates,
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
408 |
namely take the set of strings that $r$ can match (that is $L(r)$),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
409 |
filter out all strings not starting with $c$ and strip off the $c$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
410 |
from the remaining strings---this is exactly the language that
|
414
|
411 |
$\textit{der}\,c\,r$ can match.
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
412 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
413 |
If we want to find out whether the string $abc$ is matched by
|
414
|
414 |
the regular expression $r_1$ then we can iteratively apply $\textit{der}$
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
415 |
as follows
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
416 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
417 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
418 |
\begin{tabular}{rll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
419 |
Input: $r_1$, $abc$\medskip\\
|
414
|
420 |
Step 1: & build derivative of $a$ and $r_1$ & $(r_2 = \textit{der}\,a\,r_1)$\smallskip\\
|
|
421 |
Step 2: & build derivative of $b$ and $r_2$ & $(r_3 = \textit{der}\,b\,r_2)$\smallskip\\
|
433
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
422 |
Step 3: & build derivative of $c$ and $r_3$ & $(r_4 = \textit{der}\,c\,r_3)$\smallskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
423 |
Step 4: & the string is exhausted: & $(\textit{nullable}(r_4))$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
424 |
& test whether $r_4$ can recognise the\\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
425 |
& empty string\smallskip\\
|
412
|
426 |
Output: & result of this test $\Rightarrow \textit{true} \,\text{or}\, \textit{false}$\\
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
427 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
428 |
\end{center}
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
429 |
|
414
|
430 |
\noindent Again the operation $\textit{Der}$ might help to rationalise
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
431 |
this algorithm. We want to know whether $abc \in L(r_1)$. We
|
414
|
432 |
do not know yet---but let us assume it is. Then $\textit{Der}\,a\,L(r_1)$
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
433 |
builds the set where all the strings not starting with $a$ are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
434 |
filtered out. Of the remaining strings, the $a$ is stripped
|
412
|
435 |
off. So we should still have $bc$ in the set.
|
|
436 |
Then we continue with filtering out all strings not
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
437 |
starting with $b$ and stripping off the $b$ from the remaining
|
414
|
438 |
strings, that means we build $\textit{Der}\,b\,(\textit{Der}\,a\,(L(r_1)))$.
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
439 |
Finally we filter out all strings not starting with $c$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
440 |
strip off $c$ from the remaining string. This is
|
414
|
441 |
$\textit{Der}\,c\,(\textit{Der}\,b\,(\textit{Der}\,a\,(L(r_1))))$. Now if $abc$ was in the
|
|
442 |
original set ($L(r_1)$), then $\textit{Der}\,c\,(\textit{Der}\,b\,(\textit{Der}\,a\,(L(r_1))))$
|
412
|
443 |
must contain the empty string. If not, then $abc$ was not in the
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
444 |
language we started with.
|
140
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
445 |
|
414
|
446 |
Our matching algorithm using $\textit{der}$ and $\textit{nullable}$ works
|
571
|
447 |
similarly, just using regular expressions instead of sets. In order to
|
414
|
448 |
define our algorithm we need to extend the notion of derivatives from single
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
449 |
characters to strings. This can be done using the following
|
414
|
450 |
function, taking a string and a regular expression as input and
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
451 |
a regular expression as output.
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
452 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
453 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
454 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
455 |
$\textit{ders}\, []\, r$ & $\dn$ & $r$ & \\
|
414
|
456 |
$\textit{ders}\, (c\!::\!s)\, r$ & $\dn$ & $\textit{ders}\,s\,(\textit{der}\,c\,r)$ & \\
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
457 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
458 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
459 |
|
414
|
460 |
\noindent This function iterates $\textit{der}$ taking one character at
|
488
|
461 |
the time from the original string until the string is exhausted.
|
414
|
462 |
Having $\textit{der}s$ in place, we can finally define our matching
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
463 |
algorithm:
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
464 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
465 |
\[
|
571
|
466 |
\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,s\,r)
|
125
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
467 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
468 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
469 |
\noindent
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
470 |
and we can claim that
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
471 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
472 |
\[
|
571
|
473 |
\textit{matches}\,r\,s\quad\text{if and only if}\quad s\in L(r)
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
474 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
475 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
476 |
\noindent holds, which means our algorithm satisfies the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
477 |
specification. Of course we can claim many things\ldots
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
478 |
whether the claim holds any water is a different question,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
479 |
which for example is the point of the Strand-2 Coursework.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
480 |
|
566
|
481 |
This algorithm was introduced by Janusz Brzozowski in 1964, but
|
414
|
482 |
is more widely known only in the last 10 or so years. Its
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
483 |
main attractions are simplicity and being fast, as well as
|
566
|
484 |
being easily extendible for other regular expressions such as
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
485 |
$r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of
|
414
|
486 |
Strand-1 Coursework 1).
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
487 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
488 |
\subsection*{The Matching Algorithm in Scala}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
489 |
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
490 |
Another attraction of the algorithm is that it can be easily
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
491 |
implemented in a functional programming language, like Scala.
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
492 |
Given the implementation of regular expressions in Scala shown
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
493 |
in the first lecture and handout, the functions and subfunctions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
494 |
for \pcode{matches} are shown in Figure~\ref{scala1}.
|
126
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
495 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
496 |
\begin{figure}[p]
|
477
|
497 |
\lstinputlisting[numbers=left,linebackgroundcolor=
|
|
498 |
{\ifodd\value{lstnumber}\color{capri!3}\fi}]
|
|
499 |
{../progs/app5.scala}
|
512
|
500 |
\caption{A Scala implementation of \textit{nullable} and
|
|
501 |
derivative function. These functions are easy to
|
|
502 |
implement in functional programming languages. This is because pattern
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
503 |
matching and recursion allow us to mimic the mathematical
|
488
|
504 |
definitions very closely. Nearly all functional
|
|
505 |
programming languages support pattern matching and
|
|
506 |
recursion out of the box.\label{scala1}}
|
126
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
507 |
\end{figure}
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
508 |
|
414
|
509 |
|
443
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
510 |
%Remember our second example involving the regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
511 |
%$(a^*)^* \cdot b$ which could not match strings of $n$ \texttt{a}s.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
512 |
%Java needed around 30 seconds to find this out a string with $n=28$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
513 |
%It seems our algorithm is doing rather well in comparison:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
514 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
515 |
%\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
516 |
%\begin{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
517 |
%\begin{axis}[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
518 |
% title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
519 |
% xlabel={$n$},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
520 |
% x label style={at={(1.05,0.0)}},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
521 |
% ylabel={time in secs},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
522 |
% enlargelimits=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
523 |
% xtick={0,1000,...,6500},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
524 |
% xmax=6800,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
525 |
% ytick={0,5,...,30},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
526 |
% ymax=34,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
527 |
% scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
528 |
% axis lines=left,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
529 |
% width=8cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
530 |
% height=4.5cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
531 |
% legend entries={Java,Scala V1},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
532 |
% legend pos=north east,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
533 |
% legend cell align=left]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
534 |
%\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
535 |
%\addplot[red,mark=triangle*,mark options={fill=white}] table {re1a.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
536 |
%\end{axis}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
537 |
%\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
538 |
%\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
539 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
540 |
%\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
541 |
%This is not an error: it hardly takes more than half a second for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
542 |
%strings up to the length of 6500. After that we receive a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
543 |
%StackOverflow exception, but still\ldots
|
414
|
544 |
|
|
545 |
For running the algorithm with our first example, the evil
|
566
|
546 |
regular expression $a^?{}^{\{n\}}\cdot a^{\{n\}}$, we need to implement
|
488
|
547 |
the optional regular expression and the `exactly $n$-times
|
|
548 |
regular expression'. This can be done with the translations
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
549 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
550 |
\lstinputlisting[numbers=none]{../progs/app51.scala}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
551 |
|
414
|
552 |
\noindent Running the matcher with this example, we find it is
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
553 |
slightly worse then the matcher in Ruby and Python.
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
554 |
Ooops\ldots
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
555 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
556 |
\begin{center}
|
414
|
557 |
\begin{tikzpicture}
|
|
558 |
\begin{axis}[
|
415
|
559 |
title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
|
414
|
560 |
xlabel={$n$},
|
|
561 |
x label style={at={(1.05,0.0)}},
|
|
562 |
ylabel={time in secs},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
563 |
enlargelimits=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
564 |
xtick={0,5,...,30},
|
415
|
565 |
xmax=32,
|
414
|
566 |
ytick={0,5,...,30},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
567 |
scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
568 |
axis lines=left,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
569 |
width=6cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
570 |
height=5cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
571 |
legend entries={Python,Ruby,Scala V1},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
572 |
legend pos=outer north east,
|
415
|
573 |
legend cell align=left]
|
434
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
574 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
575 |
\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
576 |
\addplot[red,mark=triangle*,mark options={fill=white}] table {re1.data};
|
414
|
577 |
\end{axis}
|
|
578 |
\end{tikzpicture}
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
579 |
\end{center}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
580 |
|
488
|
581 |
\noindent Analysing this failure we notice that for $a^{\{n\}}$, for
|
|
582 |
example, we generate quite big regular expressions:
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
583 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
584 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
585 |
\begin{tabular}{rl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
586 |
1: & $a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
587 |
2: & $a\cdot a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
588 |
3: & $a\cdot a\cdot a$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
589 |
& \ldots\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
590 |
13: & $a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$\\
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
591 |
& \ldots
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
592 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
593 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
594 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
595 |
\noindent Our algorithm traverses such regular expressions at
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
596 |
least once every time a derivative is calculated. So having
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
597 |
large regular expressions will cause problems. This problem
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
598 |
is aggravated by $a^?$ being represented as $a + \ONE$.
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
599 |
|
488
|
600 |
We can however fix this easily by having an explicit constructor for
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
601 |
$r^{\{n\}}$. In Scala we would introduce a constructor like
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
602 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
603 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
604 |
\code{case class NTIMES(r: Rexp, n: Int) extends Rexp}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
605 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
606 |
|
478
|
607 |
\noindent With this fix we have a constant ``size'' regular expression
|
|
608 |
for our running example no matter how large $n$ is (see the
|
|
609 |
\texttt{size} section in the implementations). This means we have to
|
|
610 |
also add cases for \pcode{NTIMES} in the functions $\textit{nullable}$
|
|
611 |
and $\textit{der}$. Does the change have any effect?
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
612 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
613 |
\begin{center}
|
414
|
614 |
\begin{tikzpicture}
|
|
615 |
\begin{axis}[
|
415
|
616 |
title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
|
414
|
617 |
xlabel={$n$},
|
|
618 |
x label style={at={(1.01,0.0)}},
|
|
619 |
ylabel={time in secs},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
620 |
enlargelimits=false,
|
477
|
621 |
xtick={0,200,...,1100},
|
|
622 |
xmax=1200,
|
414
|
623 |
ytick={0,5,...,30},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
624 |
scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
625 |
axis lines=left,
|
414
|
626 |
width=10cm,
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
627 |
height=5cm,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
628 |
legend entries={Python,Ruby,Scala V1,Scala V2},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
629 |
legend pos=outer north east,
|
414
|
630 |
legend cell align=left]
|
434
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
631 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
632 |
\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
633 |
\addplot[red,mark=triangle*,mark options={fill=white}] table {re1.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
634 |
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
|
414
|
635 |
\end{axis}
|
|
636 |
\end{tikzpicture}
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
637 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
638 |
|
478
|
639 |
\noindent Now we are talking business! The modified matcher can within
|
|
640 |
25 seconds handle regular expressions up to $n = 1,100$ before a
|
|
641 |
StackOverflow is raised. Recall that Python and Ruby (and our first
|
|
642 |
version, Scala V1) could only handle $n = 27$ or so in 30
|
488
|
643 |
seconds. We have not tried our algorithm on the second example $(a^*)^* \cdot
|
511
|
644 |
b$---I leave this to you.
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
645 |
|
412
|
646 |
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
647 |
The moral is that our algorithm is rather sensitive to the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
648 |
size of regular expressions it needs to handle. This is of
|
414
|
649 |
course obvious because both $\textit{nullable}$ and $\textit{der}$ frequently
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
650 |
need to traverse the whole regular expression. There seems,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
651 |
however, one more issue for making the algorithm run faster.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
652 |
The derivative function often produces ``useless''
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
653 |
$\ZERO$s and $\ONE$s. To see this, consider $r = ((a
|
478
|
654 |
\cdot b) + b)^*$ and the following three derivatives
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
655 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
656 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
657 |
\begin{tabular}{l}
|
414
|
658 |
$\textit{der}\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$\\
|
|
659 |
$\textit{der}\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$\\
|
|
660 |
$\textit{der}\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
661 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
662 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
663 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
664 |
\noindent
|
488
|
665 |
If we simplify them according to the simplification rules from the
|
|
666 |
beginning, we can replace the right-hand sides by the smaller
|
|
667 |
equivalent regular expressions
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
668 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
669 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
670 |
\begin{tabular}{l}
|
414
|
671 |
$\textit{der}\,a\,r \equiv b \cdot r$\\
|
|
672 |
$\textit{der}\,b\,r \equiv r$\\
|
|
673 |
$\textit{der}\,c\,r \equiv \ZERO$
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
674 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
675 |
\end{center}
|
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 |
\noindent I leave it to you to contemplate whether such a
|
478
|
678 |
simplification can have any impact on the correctness of our algorithm
|
|
679 |
(will it change any answers?). Figure~\ref{scala2} gives a
|
|
680 |
simplification function that recursively traverses a regular
|
|
681 |
expression and simplifies it according to the rules given at the
|
571
|
682 |
beginning. There are only rules for $+$ and $\cdot$. There is
|
|
683 |
no simplification rule for a star, because
|
478
|
684 |
empirical data and also a little thought showed that simplifying under
|
|
685 |
a star is a waste of computation time. The simplification function
|
|
686 |
will be called after every derivation. This additional step removes
|
|
687 |
all the ``junk'' the derivative function introduced. Does this improve
|
|
688 |
the speed? You bet!!
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
689 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
690 |
\begin{figure}[p]
|
477
|
691 |
\lstinputlisting[numbers=left,linebackgroundcolor=
|
|
692 |
{\ifodd\value{lstnumber}\color{capri!3}\fi}]
|
|
693 |
{../progs/app6.scala}
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
694 |
\caption{The simplification function and modified
|
325
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
695 |
\texttt{ders}-function; this function now
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
696 |
calls \texttt{der} first, but then simplifies
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
697 |
the resulting derivative regular expressions before
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
698 |
building the next derivative, see
|
566
|
699 |
Line~24.\label{scala2}}
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
700 |
\end{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
701 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
702 |
\begin{center}
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
703 |
\begin{tikzpicture}
|
414
|
704 |
\begin{axis}[
|
415
|
705 |
title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
|
414
|
706 |
xlabel={$n$},
|
|
707 |
x label style={at={(1.04,0.0)}},
|
|
708 |
ylabel={time in secs},
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
709 |
enlargelimits=false,
|
478
|
710 |
xtick={0,2500,...,10000},
|
|
711 |
xmax=12000,
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
712 |
ytick={0,5,...,30},
|
443
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
713 |
ymax=32,
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
714 |
scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
715 |
axis lines=left,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
716 |
width=9cm,
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
717 |
height=5cm,
|
415
|
718 |
legend entries={Scala V2,Scala V3},
|
|
719 |
legend pos=outer north east,
|
|
720 |
legend cell align=left]
|
|
721 |
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
|
268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
722 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
723 |
\end{axis}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
724 |
\end{tikzpicture}
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
725 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
726 |
|
415
|
727 |
\noindent
|
510
|
728 |
To recap, Python and Ruby needed approximately 30 seconds to match a
|
478
|
729 |
string of 28 \texttt{a}s and the regular expression $a^{?\{n\}} \cdot
|
|
730 |
a^{\{n\}}$. We need a third of this time to do the same with strings
|
566
|
731 |
up to 11,000 \texttt{a}s. Similarly, Java 8 and Python needed 30
|
478
|
732 |
seconds to find out the regular expression $(a^*)^* \cdot b$ does not
|
566
|
733 |
match the string of 28 \texttt{a}s. In Java 9 and later this has been
|
|
734 |
cranked up to 39,000 \texttt{a}s, but we can do the same in the same
|
571
|
735 |
amount of time for strings composed of nearly 6,000,000 \texttt{a}s.
|
|
736 |
This is shown in the following plot.
|
415
|
737 |
|
|
738 |
|
414
|
739 |
\begin{center}
|
|
740 |
\begin{tikzpicture}
|
|
741 |
\begin{axis}[
|
415
|
742 |
title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
|
414
|
743 |
xlabel={$n$},
|
|
744 |
ylabel={time in secs},
|
|
745 |
enlargelimits=false,
|
478
|
746 |
ymax=35,
|
414
|
747 |
ytick={0,5,...,30},
|
|
748 |
axis lines=left,
|
550
|
749 |
%%scaled ticks=false,
|
478
|
750 |
x label style={at={(1.09,0.0)}},
|
550
|
751 |
%%xmax=7700000,
|
414
|
752 |
width=9cm,
|
|
753 |
height=5cm,
|
478
|
754 |
legend entries={Scala V3},
|
415
|
755 |
legend pos=outer north east,
|
|
756 |
legend cell align=left]
|
478
|
757 |
%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
|
414
|
758 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
|
|
759 |
\end{axis}
|
|
760 |
\end{tikzpicture}
|
|
761 |
\end{center}
|
|
762 |
|
415
|
763 |
\subsection*{Epilogue}
|
|
764 |
|
550
|
765 |
(23/Aug/2016) I found another place where this algorithm can
|
488
|
766 |
be sped up (this idea is not integrated with what is coming next, but
|
|
767 |
I present it nonetheless). The idea is to not define \texttt{ders}
|
|
768 |
that it iterates the derivative character-by-character, but in bigger
|
|
769 |
chunks. The resulting code for \texttt{ders2} looks as follows:
|
415
|
770 |
|
|
771 |
\lstinputlisting[numbers=none]{../progs/app52.scala}
|
|
772 |
|
|
773 |
\noindent
|
|
774 |
I have not fully understood why this version is much faster,
|
|
775 |
but it seems it is a combination of the clauses for \texttt{ALT}
|
|
776 |
and \texttt{SEQ}. In the latter case we call \texttt{der} with
|
|
777 |
a single character and this potentially produces an alternative.
|
510
|
778 |
The derivative of such an alternative can then be more efficiently
|
415
|
779 |
calculated by \texttt{ders2} since it pushes a whole string
|
|
780 |
under an \texttt{ALT}. The numbers are that in the second case
|
|
781 |
$(a^*)^* \cdot b$ both versions are pretty much the same, but in the
|
|
782 |
first case $a^{?\{n\}} \cdot a^{\{n\}}$ the improvement gives
|
|
783 |
another factor of 100 speedup. Nice!
|
414
|
784 |
|
415
|
785 |
\begin{center}
|
|
786 |
\begin{tabular}{cc}
|
|
787 |
\begin{tikzpicture}
|
|
788 |
\begin{axis}[
|
|
789 |
title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
|
|
790 |
xlabel={$n$},
|
|
791 |
x label style={at={(1.04,0.0)}},
|
|
792 |
ylabel={time in secs},
|
|
793 |
enlargelimits=false,
|
|
794 |
xmax=7100000,
|
|
795 |
ytick={0,5,...,30},
|
|
796 |
ymax=33,
|
|
797 |
%scaled ticks=false,
|
|
798 |
axis lines=left,
|
488
|
799 |
width=5.3cm,
|
415
|
800 |
height=5cm,
|
|
801 |
legend entries={Scala V3, Scala V4},
|
443
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
802 |
legend style={at={(0.1,-0.2)},anchor=north}]
|
415
|
803 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
|
|
804 |
\addplot[purple,mark=square*,mark options={fill=white}] table {re4.data};
|
|
805 |
\end{axis}
|
|
806 |
\end{tikzpicture}
|
|
807 |
&
|
|
808 |
\begin{tikzpicture}
|
|
809 |
\begin{axis}[
|
|
810 |
title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
|
|
811 |
xlabel={$n$},
|
|
812 |
x label style={at={(1.09,0.0)}},
|
|
813 |
ylabel={time in secs},
|
|
814 |
enlargelimits=false,
|
488
|
815 |
xmax=8200000,
|
415
|
816 |
ytick={0,5,...,30},
|
|
817 |
ymax=33,
|
|
818 |
%scaled ticks=false,
|
|
819 |
axis lines=left,
|
488
|
820 |
width=5.3cm,
|
415
|
821 |
height=5cm,
|
|
822 |
legend entries={Scala V3, Scala V4},
|
443
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
823 |
legend style={at={(0.1,-0.2)},anchor=north}]
|
415
|
824 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
|
|
825 |
\addplot[purple,mark=square*,mark options={fill=white}] table {re4a.data};
|
|
826 |
\end{axis}
|
|
827 |
\end{tikzpicture}
|
|
828 |
\end{tabular}
|
|
829 |
\end{center}
|
414
|
830 |
|
412
|
831 |
|
334
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
832 |
\section*{Proofs}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
833 |
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
834 |
You might not like doing proofs. But they serve a very
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
835 |
important purpose in Computer Science: How can we be sure that
|
488
|
836 |
our algorithm matches its specification? We can try to test
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
837 |
the algorithm, but that often overlooks corner cases and an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
838 |
exhaustive testing is impossible (since there are infinitely
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
839 |
many inputs). Proofs allow us to ensure that an algorithm
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
840 |
really meets its specification.
|
338
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
841 |
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
842 |
For the programs we look at in this module, the proofs will
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
843 |
mostly by some form of induction. Remember that regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
844 |
expressions are defined as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
845 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
846 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
847 |
\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l}
|
512
|
848 |
$r$ & $::=$ & $\ZERO$ & nothing\\
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
849 |
& $\mid$ & $\ONE$ & empty string / \texttt{""} / []\\
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
850 |
& $\mid$ & $c$ & single character\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
851 |
& $\mid$ & $r_1 + r_2$ & alternative / choice\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
852 |
& $\mid$ & $r_1 \cdot r_2$ & sequence\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
853 |
& $\mid$ & $r^*$ & star (zero or more)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
854 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
855 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
856 |
|
488
|
857 |
\noindent If you want to show a property $P(r)$ for \emph{all}
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
858 |
regular expressions $r$, then you have to follow essentially
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
859 |
the recipe:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
860 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
861 |
\begin{itemize}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
862 |
\item $P$ has to hold for $\ZERO$, $\ONE$ and $c$
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
863 |
(these are the base cases).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
864 |
\item $P$ has to hold for $r_1 + r_2$ under the assumption
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
865 |
that $P$ already holds for $r_1$ and $r_2$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
866 |
\item $P$ has to hold for $r_1 \cdot r_2$ under the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
867 |
assumption that $P$ already holds for $r_1$ and $r_2$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
868 |
\item $P$ has to hold for $r^*$ under the assumption
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
869 |
that $P$ already holds for $r$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
870 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
871 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
872 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
873 |
A simple proof is for example showing the following
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
874 |
property:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
875 |
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
876 |
\begin{equation}
|
412
|
877 |
\textit{nullable}(r) \;\;\text{if and only if}\;\; []\in L(r)
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
878 |
\label{nullableprop}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
879 |
\end{equation}
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
880 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
881 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
882 |
Let us say that this property is $P(r)$, then the first case
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
883 |
we need to check is whether $P(\ZERO)$ (see recipe
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
884 |
above). So we have to show that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
885 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
886 |
\[
|
412
|
887 |
\textit{nullable}(\ZERO) \;\;\text{if and only if}\;\;
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
888 |
[]\in L(\ZERO)
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
889 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
890 |
|
412
|
891 |
\noindent whereby $\textit{nullable}(\ZERO)$ is by definition of
|
|
892 |
the function $\textit{nullable}$ always $\textit{false}$. We also have
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
893 |
that $L(\ZERO)$ is by definition $\{\}$. It is
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
894 |
impossible that the empty string $[]$ is in the empty set.
|
339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
895 |
Therefore also the right-hand side is false. Consequently we
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
896 |
verified this case: both sides are false. We would still need
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
897 |
to do this for $P(\ONE)$ and $P(c)$. I leave this to
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
898 |
you to verify.
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
899 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
900 |
Next we need to check the inductive cases, for example
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
901 |
$P(r_1 + r_2)$, which is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
902 |
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
903 |
\begin{equation}
|
412
|
904 |
\textit{nullable}(r_1 + r_2) \;\;\text{if and only if}\;\;
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
905 |
[]\in L(r_1 + r_2)
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
906 |
\label{propalt}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
907 |
\end{equation}
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
908 |
|
488
|
909 |
\noindent The difference to the base cases is that in the inductive
|
|
910 |
cases we can already assume we proved $P$ for the components, that is
|
|
911 |
we can assume.
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
912 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
913 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
914 |
\begin{tabular}{l}
|
412
|
915 |
$\textit{nullable}(r_1) \;\;\text{if and only if}\;\; []\in L(r_1)$ and\\
|
|
916 |
$\textit{nullable}(r_2) \;\;\text{if and only if}\;\; []\in L(r_2)$\\
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
917 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
918 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
919 |
|
488
|
920 |
\noindent These are called the induction hypotheses. To check this
|
412
|
921 |
case, we can start from $\textit{nullable}(r_1 + r_2)$, which by
|
488
|
922 |
definition of $\textit{nullable}$ is
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
923 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
924 |
\[
|
412
|
925 |
\textit{nullable}(r_1) \vee \textit{nullable}(r_2)
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
926 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
927 |
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
928 |
\noindent Using the two induction hypotheses from above,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
929 |
we can transform this into
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
930 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
931 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
932 |
[] \in L(r_1) \vee []\in(r_2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
933 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
934 |
|
412
|
935 |
\noindent We just replaced the $\textit{nullable}(\ldots)$ parts by
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
936 |
the equivalent $[] \in L(\ldots)$ from the induction
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
937 |
hypotheses. A bit of thinking convinces you that if
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
938 |
$[] \in L(r_1) \vee []\in L(r_2)$ then the empty string
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
939 |
must be in the union $L(r_1)\cup L(r_2)$, that is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
940 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
941 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
942 |
[] \in L(r_1)\cup L(r_2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
943 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
944 |
|
488
|
945 |
\noindent but this is by definition of $L$ exactly $[] \in L(r_1 +
|
|
946 |
r_2)$, which we needed to establish according to statement in
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
947 |
\eqref{propalt}. What we have shown is that starting from
|
412
|
948 |
$\textit{nullable}(r_1 + r_2)$ we have done equivalent transformations
|
488
|
949 |
to end up with $[] \in L(r_1 + r_2)$. Consequently we have established
|
|
950 |
that $P(r_1 + r_2)$ holds.
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
951 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
952 |
In order to complete the proof we would now need to look
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
953 |
at the cases \mbox{$P(r_1\cdot r_2)$} and $P(r^*)$. Again I let you
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
954 |
check the details.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
955 |
|
488
|
956 |
You might also have to do induction proofs over strings.
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
957 |
That means you want to establish a property $P(s)$ for all
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
958 |
strings $s$. For this remember strings are lists of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
959 |
characters. These lists can be either the empty list or a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
960 |
list of the form $c::s$. If you want to perform an induction
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
961 |
proof for strings you need to consider the cases
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
962 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
963 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
964 |
\item $P$ has to hold for $[]$ (this is the base case).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
965 |
\item $P$ has to hold for $c::s$ under the assumption
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
966 |
that $P$ already holds for $s$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
967 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
968 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
969 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
970 |
Given this recipe, I let you show
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
971 |
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
972 |
\begin{equation}
|
414
|
973 |
\textit{Ders}\,s\,(L(r)) = L(\textit{ders}\,s\,r)
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
974 |
\label{dersprop}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
975 |
\end{equation}
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
976 |
|
414
|
977 |
\noindent by induction on $s$. Recall $\textit{Der}$ is defined for
|
|
978 |
character---see \eqref{Der}; $\textit{Ders}$ is similar, but for strings:
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
979 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
980 |
\[
|
414
|
981 |
\textit{Ders}\,s\,A\;\dn\;\{s'\,|\,s @ s' \in A\}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
982 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
983 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
984 |
\noindent In this proof you can assume the following property
|
414
|
985 |
for $der$ and $\textit{Der}$ has already been proved, that is you can
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
986 |
assume
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
987 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
988 |
\[
|
414
|
989 |
L(\textit{der}\,c\,r) = \textit{Der}\,c\,(L(r))
|
340
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
990 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
991 |
|
488
|
992 |
\noindent holds (this would be of course another property that needs
|
|
993 |
to be proved in a side-lemma by induction on $r$). This is a bit
|
|
994 |
more challenging, but not impossible.
|
338
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
995 |
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
996 |
To sum up, using reasoning like the one shown above allows us
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
997 |
to show the correctness of our algorithm. To see this,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
998 |
start from the specification
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
999 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1000 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1001 |
s \in L(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1002 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1003 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1004 |
\noindent That is the problem we want to solve. Thinking a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1005 |
little, you will see that this problem is equivalent to the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1006 |
following problem
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1007 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1008 |
\begin{equation}
|
414
|
1009 |
[] \in \textit{Ders}\,s\,(L(r))
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1010 |
\label{dersstep}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1011 |
\end{equation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1012 |
|
488
|
1013 |
\noindent You agree? But we have shown above in \eqref{dersprop},
|
|
1014 |
that the $\textit{Ders}$ can be replaced by
|
|
1015 |
$L(\textit{ders}\ldots)$. That means \eqref{dersstep} is equivalent to
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1016 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1017 |
\begin{equation}
|
414
|
1018 |
[] \in L(\textit{ders}\,s\,r)
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1019 |
\label{prefinalstep}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1020 |
\end{equation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1021 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1022 |
\noindent We have also shown that testing whether the empty
|
412
|
1023 |
string is in a language is equivalent to the $\textit{nullable}$
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1024 |
function; see \eqref{nullableprop}. That means
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1025 |
\eqref{prefinalstep} is equivalent with
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1026 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1027 |
\[
|
414
|
1028 |
\textit{nullable}(\textit{ders}\,s\,r)
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1029 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1030 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1031 |
\noindent But this is just the definition of $matches$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1032 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1033 |
\[
|
414
|
1034 |
matches\,s\,r \dn nullable(\textit{ders}\,s\,r)
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1035 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1036 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1037 |
\noindent In effect we have shown
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1038 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1039 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1040 |
matches\,s\,r\;\;\text{if and only if}\;\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1041 |
s\in L(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1042 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1043 |
|
488
|
1044 |
\noindent which is the property we set out to prove: our algorithm
|
|
1045 |
meets its specification. To have done so, requires a few induction
|
|
1046 |
proofs about strings and regular expressions. Following the \emph{induction
|
|
1047 |
recipes} is already a big step in actually performing these proofs.
|
|
1048 |
If you do not believe it, proofs have helped me to make sure my code
|
|
1049 |
is correct and in several instances prevented me of letting slip
|
566
|
1050 |
embarrassing mistakes into the `wild'.
|
343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1051 |
|
262
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1052 |
\end{document}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1053 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1054 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1055 |
|
566
|
1056 |
% !TeX program = latexmk -xelatex
|
123
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1057 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1058 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1059 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1060 |
%%% End:
|