|
1 \documentclass[12pt]{article} |
|
2 \usepackage{../style} |
|
3 \usepackage{../langs} |
|
4 \usepackage{graphicx} |
|
5 |
|
6 \newtheorem{thm}{Theorem} |
|
7 \newtheorem{lem}[thm]{Lemma} |
|
8 \newtheorem{cor}[thm]{Corollary} |
|
9 \newenvironment{proof}{\paragraph{Proof:}\it}{\hfill$\square$} |
|
10 |
|
11 |
|
12 \begin{document} |
|
13 |
|
14 |
|
15 \section*{Antimirov's Proof about Pders} |
|
16 |
|
17 These are some rough notes about the result by Antimirov establishing |
|
18 a bound on the number of regular expressions in a partial |
|
19 derivative. From this bound on the number of partial derivatives one |
|
20 can easily construct an NFA for a regular expression, but one can also |
|
21 derive a bound on the size of the partial derivatives. This is what we |
|
22 do first. We start with the following definitions: |
|
23 |
|
24 \begin{itemize} |
|
25 \item $pder\,c\,r$ --- partial derivative according to a character; this can be defined |
|
26 inductively as follows: |
|
27 |
|
28 \begin{center} |
|
29 \begin{tabular}{l@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
30 $\textit{pder}\, c\, (\ZERO)$ & $\dn$ & $\emptyset$\\ |
|
31 $\textit{pder}\, c\, (\ONE)$ & $\dn$ & $\emptyset$ \\ |
|
32 $\textit{pder}\, c\, (d)$ & $\dn$ & if $c = d$ then $\{\ONE\}$ else $\emptyset$\\ |
|
33 $\textit{pder}\, c\, (r_1 + r_2)$ & $\dn$ & $\textit{pder}\, c\, r_1 \;\cup\; \textit{pder}\, c\, r_2$\\ |
|
34 $\textit{pder}\, c\, (r_1 \cdot r_2)$ & $\dn$ & if $\textit{nullable} (r_1)$\\ |
|
35 & & then $\Pi\,(\textit{pder}\,c\,r_1)\,r_2 \;\cup\; \textit{pder}\, c\, r_2$\\ |
|
36 & & else $\Pi\,(\textit{pder}\, c\, r_1)\,r_2$\\ |
|
37 $\textit{pder}\, c\, (r^*)$ & $\dn$ & $\Pi\,(\textit{pder}\,c\,r)\, (r^*)$ |
|
38 \end{tabular} |
|
39 \end{center} |
|
40 |
|
41 \item $pder^+\,c\,\,rs$ --- partial derivatives for a set regular exprssions $rs$ |
|
42 \item $pders\,s\,r$ --- partial derivative of a regular expression |
|
43 according to a string |
|
44 |
|
45 \item $Pders\,A\,r \dn \bigcup_{s\in A}. pders\,s\,r$ --- partial |
|
46 derivatives according to a language (a set of strings) |
|
47 \item $|rs|$ is the size of a set of regular expressions $rs$, or |
|
48 the number of elements in the |
|
49 set (also known as the cardinality of this set) |
|
50 \item $\prod\,rs\;r \dn \{r_1 \cdot r \;|\; r_1 \in rs\}$ --- this is |
|
51 some convenience when writing a set of sequence regular |
|
52 expressions. It essentially ``appends'' the regular expression $r$ to all |
|
53 regular expressions in the set $rs$. As a result one can write |
|
54 the sequence case for partial derivatives (see above) more conveniently |
|
55 as |
|
56 \[ |
|
57 pder\,c\,(r_1\cdot r_2) \dn |
|
58 \begin{cases} |
|
59 \prod\,(pder\,c\,r_1)\,r_2\;\cup\;pder\,c\,r_2 & |
|
60 \!\!\textit{provided}\,r_1\, \textit{is nullable}\\ |
|
61 \prod\,(pder\,c\,r_1)\,r_2 & \!\!\textit{otherwise}\\ |
|
62 \end{cases} |
|
63 \] |
|
64 \item $\textit{Psuf}\,s$ is the set of all non-empty suffixes of $s$ defined as |
|
65 \[ |
|
66 \textit{PSuf}\, s \dn \{v.\;v \not= [] \wedge \exists u. u \,@\, v = s \} |
|
67 \] |
|
68 |
|
69 So for the string $abc$ the non-empty suffixes are $c$, $bc$ and |
|
70 $abc$. Also we have that |
|
71 $\textit{Psuf}\,(s\,@\,[c]) = ((\textit{Psuf}\,s)\,@@\,[c]) \cup |
|
72 \{[c]\}$. Here $@@$ means to concatenate $[c]$ to the end of |
|
73 all strings in $\textit{Psuf}\,s$; in this equation we also |
|
74 need to add $\{[c]\}$ in order to make the equation to hold. |
|
75 \end{itemize} |
|
76 |
|
77 \noindent |
|
78 To state Antimirov's result we need the following definition of an |
|
79 \emph{alphabetic width} of a regular expression defined as follows: |
|
80 |
|
81 \begin{center} |
|
82 \begin{tabular}{lcl} |
|
83 $awidth(\ZERO)$ & $\dn$ & $0$\\ |
|
84 $awidth(\ONE)$ & $\dn$ & $0$\\ |
|
85 $awidth(c)$ & $\dn$ & $1$\\ |
|
86 $awidth(r_1 + r_2)$ & $\dn$ & $awidth(r_1) + awidth(r_2)$\\ |
|
87 $awidth(r_1 \cdot r_2)$ & $\dn$ & $awidth(r_1) + awidth(r_2)$\\ |
|
88 $awidth(r^*)$ & $\dn$ & $awidth(r)$\\ |
|
89 \end{tabular} |
|
90 \end{center} |
|
91 |
|
92 \noindent |
|
93 This function counts how many characters are in a regular expression. |
|
94 Antimirov's result states |
|
95 |
|
96 \begin{thm}\label{one} |
|
97 $\forall\,A\,r\,.\;\;|Pders\;A\;r| \leq awidth(r) + 1$ |
|
98 \end{thm} |
|
99 |
|
100 \noindent |
|
101 Note this theorem holds for any set of strings $A$, for example |
|
102 for the set of all strings, which I will write as $\textit{UNIV}$, and also |
|
103 for the set $\{s\}$ containing only a single string $s$. Therefore a |
|
104 simple corollary is |
|
105 |
|
106 \begin{cor} |
|
107 $\forall\,s\,r\,.\;\;|pders\;s\;r| \leq awidth(r) + 1$ |
|
108 \end{cor} |
|
109 |
|
110 \noindent |
|
111 This property says that for every string $s$, the number of regular |
|
112 expressions in the derivative can never be bigger than |
|
113 $awidth(r) + 1$. Interestingly we do not show Thm~\ref{one} for all |
|
114 sets of strings $A$ directly, but rather only for one particular set of |
|
115 strings which I call $UNIV_1$. It includes all strings except the empty string |
|
116 (remember $UNIV$ contains all strings).\bigskip |
|
117 |
|
118 \noindent |
|
119 Let's try to give below a comprehensible account of Antimirov's proof |
|
120 of Thm.~\ref{one}---I distictly remember that Antimirov's paper is |
|
121 great, but pretty incomprehensible for the first 20+ times one reads |
|
122 that paper. The proof starts with the following much weaker property |
|
123 about the size being finite: |
|
124 |
|
125 \begin{lem} |
|
126 $\forall\,A\,r\,.\;\;(Pders\;A\;r)$ is a finite set. |
|
127 \end{lem} |
|
128 |
|
129 \noindent This lemma is needed because some reasoning steps in |
|
130 Thm~\ref{one} only work for finite sets, not infinite sets. But let us |
|
131 skip over the proof of this property at first and let us assume we |
|
132 know already that the partial derivatives are always finite sets (this for |
|
133 example does not hold for unsimplified Brzozowski derivatives which |
|
134 can be infinite for some sets of strings). |
|
135 |
|
136 There are some central lemmas about partial derivatives for $\cdot$ and $\_^*$. |
|
137 One is the following |
|
138 |
|
139 \begin{lem}\label{central}\mbox{}\\ |
|
140 \[Pders\,UNIV_1\,(r_1\cdot r_2) \subseteq (\prod (Pders\,UNIV_1\, r_1)\,r_2) \; |
|
141 \cup \; Pders\,UNIV_1\,r_2\] |
|
142 \end{lem} |
|
143 |
|
144 \begin{proof} |
|
145 \noindent The proof is done via an induction for the following property |
|
146 \[ |
|
147 pders\,s\,(r_1\cdot r_2) \subseteq (\prod (pders\,s\, r_1)\,r_2) \; |
|
148 \cup \; Pders\,(\textit{PSuf}\,s)\,r_2 |
|
149 \] |
|
150 |
|
151 \noindent |
|
152 Note that this property uses $pders$ and $Pders$ together. The proof is done |
|
153 by ``reverse'' induction on $s$, meaning the cases to analyse are the |
|
154 empty string $[]$ and the case where a character is put at the end of the |
|
155 string $s$, namely $s \,@\, [c]$. The case $[]$ is trivial. In the other |
|
156 case we know by IH that |
|
157 |
|
158 \[ |
|
159 pders\,s\,(r_1\cdot r_2) \subseteq (\prod (pders\,s\, r_1)\,r_2) \; |
|
160 \cup \; Pders\,(\textit{PSuf}\,s)\,r_2 |
|
161 \] |
|
162 |
|
163 \noindent |
|
164 holds for $s$. Then we have to show it holds for $s\,@\,[c]$ |
|
165 |
|
166 \begin{center} |
|
167 \begin{tabular}{r@{\hspace{2mm}}ll} |
|
168 & $pders\,(s\,@\,[c])\,(r_1\cdot r_2)$\\ |
|
169 $=$ & $pder^+\,c\,(pders\,s\,(r_1\cdot r_2))$\\ |
|
170 $\subseteq$ & $pder^+\,c\,(\prod (pders\,s\, r_1)\,r_2 \; |
|
171 \cup \; Pders\,(\textit{PSuf}\,s)\,r_2)$\\ |
|
172 & \hfill{}by IH\\ |
|
173 $=$ & $(pder^+\,c\,(\prod (pders\,s\, r_1)\,r_2))\;\cup\; |
|
174 (pder^+\,c\,(Pders\,(\textit{PSuf}\,s)\,r_2))$\\ |
|
175 $=$ & $(pder^+\,c\,(\prod (pders\,s\, r_1)\,r_2))\;\cup\; |
|
176 (Pders\,(\textit{PSuf}\,(s\,@\,[c]))\,r_2)$\\ |
|
177 $\subseteq$ & |
|
178 $(pder^+\,c\,(\prod (pders\,s\, r_1)\,r_2))\;\cup\; |
|
179 (pder\,c\,r_2)\;\cup\; |
|
180 (Pders\,(\textit{PSuf}\,s\,@@\,[c])\,r_2)$\\ |
|
181 $\subseteq$ & $\prod (pder^+\,c\,(pders\,s\, r_1))\,r_2\;\cup\; |
|
182 (pder\,c\,r_2)\;\cup\; |
|
183 (Pders\,(\textit{PSuf}\,s\,@@\,[c])\,r_2)$\\ |
|
184 $=$ & $(\prod (pders\,(s\,@\,[c])\, r_1)\,r_2)\;\cup\; |
|
185 (pder\,c\,r_2)\;\cup\; |
|
186 (Pders\,(\textit{PSuf}\,s\,@@\,[c])\,r_2)$\\ |
|
187 $\subseteq$ & $(\prod (pders\,(s\,@\,[c])\, r_1)\,r_2)\;\cup\; |
|
188 (Pders\,(\textit{PSuf}\,(s\,@\,[c]))\,r_2)$\\ |
|
189 \end{tabular} |
|
190 \end{center} |
|
191 |
|
192 \noindent The lemma now follows because for an $s \in UNIV_1$ it holds that |
|
193 |
|
194 \[ |
|
195 \prod\,(pders\,s\,r_1)\,r_2 \subseteq \prod (Pders\,UNIV_1\, r_1)\,r_2 |
|
196 \] |
|
197 |
|
198 \noindent and |
|
199 |
|
200 \[ |
|
201 Pders\,(\textit{PSuf}\,s)\,r_2 \subseteq Pders\,UNIV_1\,r_2 |
|
202 \] |
|
203 |
|
204 \noindent The left-hand sides of the inclusions above are |
|
205 euqal to $pders\,s\,(r_1\cdot r_2)$ for a string $s\in UNIV_1$. |
|
206 \end{proof}\medskip |
|
207 |
|
208 \noindent There is a similar lemma for the $^*$-regular expression, namely: |
|
209 |
|
210 \begin{lem}\label{centraltwo} |
|
211 $Pders\,UNIV_1\,(r^*) \subseteq \prod\, (Pders\,UNIV_1\,r)\,(r^*)$ |
|
212 \end{lem} |
|
213 |
|
214 \noindent |
|
215 We omit the proof for the moment (similar to Lem~\ref{central}). We |
|
216 also need the following property about the cardinality of $\prod$: |
|
217 |
|
218 \begin{lem}\label{centralthree} |
|
219 $|\prod\,(Pders\,A\,r_1)\,r_2| \le |Pders\,A\,r_1|$ |
|
220 \end{lem} |
|
221 |
|
222 \noindent |
|
223 We only need the $\le$ version, which essentially says there |
|
224 are as many sequences $r\cdot r_2$ as are elements in $r$. Now |
|
225 for the proof of Thm~\ref{one}: The main induction in |
|
226 Antimirov's proof establishes that:\footnote{Remember that it is |
|
227 always the hardest part in an induction proof to find the right |
|
228 property that is strong enough and of the right shape for the |
|
229 induction to go through.} |
|
230 |
|
231 \begin{lem}\label{two} |
|
232 $\forall r.\;\;|Pders\;UNIV_1\;r| \leq awidth(r)$ |
|
233 \end{lem} |
|
234 |
|
235 \begin{proof} This is proved by induction on |
|
236 $r$. The interesting cases are $r_1 + r_2$, $r_1\cdot r_2$ and |
|
237 $r^*$. Let us start with the relatively simple case:\medskip |
|
238 |
|
239 \noindent |
|
240 \textbf{Case $r_1 + r_2$:} By induction hypothesis we know |
|
241 |
|
242 \begin{center} |
|
243 \begin{tabular}{l} |
|
244 $|Pders\;UNIV_1\;r_1| \leq awidth(r_1)$\\ |
|
245 $|Pders\;UNIV_1\;r_2| \leq awidth(r_2)$ |
|
246 \end{tabular} |
|
247 \end{center} |
|
248 |
|
249 \noindent |
|
250 In this case we can reason as follows |
|
251 |
|
252 \begin{center} |
|
253 \begin{tabular}{r@{\hspace{2mm}}ll} |
|
254 & $|Pders\;UNIV_1\;(r_1+r_2)|$\\ |
|
255 $=$ & $|(Pders\;UNIV_1\;r_1) \;\cup\; (Pders\;UNIV_1\;r_2)|$\\ |
|
256 $\leq$ & $|(Pders\;UNIV_1\;r_1)| \;+\; |(Pders\;UNIV_1\;r_2)|$ & (*)\\ |
|
257 $\leq$ & $awidth(r_1) + awidth(r_2)$\\ |
|
258 $\dn$ & $awidth(r_1 + r_2)$ |
|
259 \end{tabular} |
|
260 \end{center} |
|
261 |
|
262 \noindent Note that (*) is a step that only works if one knows that |
|
263 $|(Pders\;UNIV_1\;r_1)|$ and so on are finite. The next case is |
|
264 a bit more interesting:\medskip |
|
265 |
|
266 \noindent |
|
267 \textbf{Case $r_1 \cdot r_2$:} We have the same induction |
|
268 hypothesis as in the case before. |
|
269 |
|
270 \begin{center} |
|
271 \begin{tabular}{r@{\hspace{2mm}}ll} |
|
272 & $|Pders\;UNIV_1\;(r_1\cdot r_2)|$\\ |
|
273 $\leq$ & $|\prod\,(Pders\;UNIV_1\;r_1)\,r_2\;\cup\; (Pders\;UNIV_1\;r_2)|$ |
|
274 & by Lem~\ref{central}\\ |
|
275 $\leq$ & $|\prod\,(Pders\;UNIV_1\;r_1)\,r_2| \;+\; |(Pders\;UNIV_1\;r_2)|$\\ |
|
276 $\leq$ & $|Pders\;UNIV_1\;r_1| \;+\; |Pders\;UNIV_1\;r_2|$ |
|
277 & by Lem~\ref{centralthree} \\ |
|
278 $\leq$ & $awidth(r_1) + awidth(r_2)$\\ |
|
279 $\dn$ & $awidth(r_1 \cdot r_2)$ |
|
280 \end{tabular} |
|
281 \end{center} \medskip |
|
282 |
|
283 \noindent |
|
284 \textbf{Case $r^*$:} Again we have the same induction |
|
285 hypothesis as in the cases before. |
|
286 |
|
287 \begin{center} |
|
288 \begin{tabular}{r@{\hspace{2mm}}ll} |
|
289 & $|Pders\;UNIV_1\;(r^*)|$\\ |
|
290 $\leq$ & $|\prod\,(Pders\;UNIV_1\;r)\,(r^*)|$ |
|
291 & by Lem~\ref{centraltwo}\\ |
|
292 $\leq$ & $|Pders\;UNIV_1\;r|$ |
|
293 & by Lem~\ref{centralthree} \\ |
|
294 $\leq$ & $awidth(r)$\\ |
|
295 \end{tabular} |
|
296 \end{center} |
|
297 \end{proof}\bigskip |
|
298 |
|
299 \noindent |
|
300 From this lemma we can derive the next corrollary which extends |
|
301 the property to $UNIV$ ($= UNIV_1 \cup \{[]\}$): |
|
302 |
|
303 \begin{cor} |
|
304 $\forall r.\;\;|Pders\;UNIV\;r| \leq awidth(r) + 1$ |
|
305 \end{cor} |
|
306 |
|
307 \begin{proof} This can be proved as follows |
|
308 \begin{center} |
|
309 \begin{tabular}{r@{\hspace{2mm}}ll} |
|
310 & $|Pders\;UNIV\;r|$\\ |
|
311 $=$ & $|Pders\;(UNIV_1 \cup \{[]\})\;r|$\\ |
|
312 $=$ & $|(Pders\;UNIV_1\,r) \;\cup\;\{r\}|$\\ |
|
313 $\leq$ & $|Pders\;UNIV_1\,r| + 1$ & by Lem~\ref{two}\\ |
|
314 $\leq$ & $awidth(r) + 1$\\ |
|
315 \end{tabular} |
|
316 \end{center} |
|
317 \end{proof} |
|
318 |
|
319 \noindent |
|
320 From the last corollary, it is easy to infer Antimirov's |
|
321 Thm~\ref{one}, because |
|
322 |
|
323 \[ Pders\,A\,r \subseteq Pders\,UNIV\,r \] |
|
324 |
|
325 |
|
326 \noindent |
|
327 for all sets $A$.\bigskip |
|
328 |
|
329 \noindent |
|
330 While I was earlier a bit dismissive above about the intelligibility |
|
331 of Antimirov's paper, you have to admit this proof is a work of |
|
332 beauty. It only gives a bound (\textit{awidth}) for the number of |
|
333 regular expressions in the de\-rivatives---this is important for |
|
334 constructing NFAs. Maybe it has not been important before, but I have |
|
335 never seen a result about the \emph{size} of the partial |
|
336 derivatives.\footnote{Update: I have now seen a paper which proves |
|
337 this result as well.} However, a very crude bound, namely |
|
338 $(size(r)^2 + 1) \times (awidth(r) + 1)$, can be easily derived by |
|
339 using Antimirov's result. The definition we need for this is a |
|
340 function that collects subexpressions from which partial derivatives |
|
341 are built: |
|
342 |
|
343 |
|
344 \begin{center} |
|
345 \begin{tabular}{lcl} |
|
346 $subs(\ZERO)$ & $\dn$ & $\{\ZERO\}$\\ |
|
347 $subs(\ONE)$ & $\dn$ & $\{\ONE\}$\\ |
|
348 $subs(c)$ & $\dn$ & $\{c, \ONE\}$\\ |
|
349 $subs(r_1 + r_2)$ & $\dn$ & $\{r_1 + r_2\}\,\cup\,subs(r_1) \,\cup\, subs(r_2)$\\ |
|
350 $subs(r_1 \cdot r_2)$ & $\dn$ & $\{r_1 \cdot r_2\}\,\cup (\prod\,subs(r_1)\;r_2)\,\cup \, |
|
351 subs(r_1) \,\cup\, subs(r_2)$\\ |
|
352 $subs(r^*)$ & $\dn$ & $\{r^*\}\,\cup\,(\prod\,subs(r)\;r^*) \,\cup\, subs(r)$\\ |
|
353 \end{tabular} |
|
354 \end{center} |
|
355 |
|
356 \noindent |
|
357 We can show that |
|
358 |
|
359 \begin{lem} |
|
360 $pders\,s\,r \subseteq subs(r)$ |
|
361 \end{lem} |
|
362 |
|
363 \noindent |
|
364 This is a relatively simple induction on $r$. The point is that for every element |
|
365 in $subs$, the maximum size is given by |
|
366 |
|
367 \begin{lem} |
|
368 If $r' \in subs(r)$ then $size(r') \le 1 + size(r)^2$. |
|
369 \end{lem} |
|
370 |
|
371 \noindent |
|
372 Again the proof is a relatively simple induction on $r$. Stringing Antimirov's result |
|
373 and the lemma above together gives |
|
374 |
|
375 \begin{thm} |
|
376 $\sum_{r' \in pders\,s\,r}.\;size(r') \le (size(r)^2 + 1) \times (awidth(r) + 1)$ |
|
377 \end{thm} |
|
378 |
|
379 \noindent |
|
380 Since $awidth$ is always smaller than the $size$ of a regular expression, |
|
381 one can also state the bound as follows: |
|
382 |
|
383 \[ |
|
384 \sum_{r' \in pders\,s\,r}.\;size(r') \le (size(r) + 1)^3 |
|
385 \] |
|
386 |
|
387 \noindent |
|
388 This, by the way, also holds for $Pders$, namely |
|
389 |
|
390 \[ |
|
391 \sum_{r' \in Pders\,A\,r}.\;size(r') \le (size(r) + 1)^3 |
|
392 \] |
|
393 |
|
394 \noindent |
|
395 for all $r$ and $A$. If one is interested in the height of the partial derivatives, one can derive: |
|
396 |
|
397 \[ |
|
398 \forall\,r' \in pders\,s\,r.\;height(r') \le height(r) + 1 |
|
399 \] |
|
400 |
|
401 |
|
402 \noindent |
|
403 meaning the height of the partial derivatives is never bigger than |
|
404 the height of the original regular expression (+1). |
|
405 |
|
406 \section*{NFA Construction via Antimirov's Partial Derivatives} |
|
407 |
|
408 Let's finish these notes with the construction of an NFA for a regular |
|
409 expression using partial derivatives. As usual an automaton is a |
|
410 quintuple $(Q, A, \delta, q_0, F)$ where $Q$ is the set of states of |
|
411 the automaton, $A$ is the alphabet, $q_0$ is the starting state and |
|
412 $F$ are the accepting states. For DFAs the $\delta$ is a (partial) |
|
413 function from state $\times$ character to state. For NFAs it is a |
|
414 relation between state $\times$ character $\times$ state. The |
|
415 non-determinism can be seen by the following: consider three |
|
416 (distinct) states $q_1$, $q_2$ and $q_3$, then the relation can |
|
417 include $(q_1, a, q_2)$ and $(q_1, a, q_3)$, which means there is a |
|
418 transition between $q_1$ and both $q_2$ and $q_3$ for the character |
|
419 $a$. |
|
420 |
|
421 The Antimirov's NFA for a regular expression $r$ is then |
|
422 given by the quintuple |
|
423 \[(PD(r), A, \delta_{PD}, r, F)\] |
|
424 |
|
425 \noindent |
|
426 where $PD(r)$ are all the partial |
|
427 derivatives according to all strings, that is |
|
428 \[ |
|
429 PD(r) \;\dn\; \textit{Pders}\;\textit{UNIV}\;r |
|
430 \] |
|
431 |
|
432 \noindent |
|
433 Because of the previous proof, we know that this set is finite. We |
|
434 also see that the states in Antimirov's NFA are ``labelled'' by single |
|
435 regular expressions. The starting state is labelled with the original |
|
436 regular expression $r$. The set of accepting states $F$ is all states |
|
437 $r'\in F$ where $r'$ is nullable. The relation $\delta_{PD}$ is given by |
|
438 \[ |
|
439 (r_1, c, r_2) |
|
440 \] |
|
441 |
|
442 \noindent |
|
443 for every $r_1 \in PD(r)$ and $r_2 \in \textit{pder}\,c\,r$. This is |
|
444 in general a ``non-deterministic'' relation because the set of partial |
|
445 derivatives often contains more than one element. A nice example of |
|
446 an NFA constructed via Antimirov's partial derivatives is given in |
|
447 \cite{IlieYu2003} on Page 378. |
|
448 |
|
449 The difficulty of course in this construction is to find the set of |
|
450 partial derivatives according to \emph{all} strings. However, it seem |
|
451 a procedure that enumerates strings according to size suffices until |
|
452 no new derivative is found. There are various improvements that apply |
|
453 clever tricks on how to more efficiently discover this set. |
|
454 |
|
455 |
|
456 \begin{thebibliography}{999} |
|
457 |
|
458 \bibitem{IlieYu2003} |
|
459 L.~Ilie and S.~Yu, |
|
460 \emph{Reducing NFAs by Invariant Equivalences}. |
|
461 In Theoretical Computer Science, Volume 306(1--3), Pages 373–-390, 2003.\\ |
|
462 \url{https://core.ac.uk/download/pdf/82545723.pdf} |
|
463 |
|
464 \end{thebibliography} |
|
465 |
|
466 |
|
467 |
|
468 |
|
469 |
|
470 |
|
471 \end{document} |
|
472 |
|
473 |
|
474 %%% Local Variables: |
|
475 %%% mode: latex |
|
476 %%% TeX-master: t |
|
477 %%% End: |