100 the singleton language with $L = \{w\}$ |
100 the singleton language with $L = \{w\}$ |
101 in formal language theory. |
101 in formal language theory. |
102 However, for the purposes here, the $\textit{Ders}$ definition with |
102 However, for the purposes here, the $\textit{Ders}$ definition with |
103 a single string is sufficient. |
103 a single string is sufficient. |
104 |
104 |
|
105 The reason for defining derivatives |
|
106 is that it provides a different approach |
|
107 to test membership of a string in |
|
108 a set of strings. |
|
109 For example, to test whether the string |
|
110 $bar$ is contained in the set $\{foo, bar, brak\}$, one takes derivative of the set with |
|
111 respect to the string $bar$: |
|
112 \begin{center} |
|
113 \begin{tabular}{lclll} |
|
114 $S = \{foo, bar, brak\}$ & $ \stackrel{\backslash b}{\rightarrow }$ & |
|
115 $\{ar, rak\}$ & |
|
116 $\stackrel{\backslash a}{\rightarrow}$ & |
|
117 \\ |
|
118 $\{r \}$ & $\stackrel{\backslash r}{\rightarrow}$ & $\{[]\}$ & |
|
119 $\stackrel{[] \in S \backslash bar}{\longrightarrow}$ & $bar \in S$\\ |
|
120 \end{tabular} |
|
121 \end{center} |
|
122 \noindent |
|
123 and in the end test whether the set |
|
124 has the empty string \footnote{ we use the infix notation $A\backslash c$ |
|
125 instead of $\Der \; c \; A$ for brevity, as it is clear we are operating |
|
126 on languages rather than regular expressions }. |
|
127 In general, if we have a language $S_{start}$, |
|
128 then we can test whether $s$ is in $S_{start}$ |
|
129 by testing whether $[] \in S \backslash s$. |
|
130 |
105 With the sequencing, Kleene star, and $\textit{Der}$ operator on languages, |
131 With the sequencing, Kleene star, and $\textit{Der}$ operator on languages, |
106 we have a few properties of how the language derivative can be defined using |
132 we have a few properties of how the language derivative can be defined using |
107 sub-languages. |
133 sub-languages. |
|
134 For example, for the sequence operator, we have |
|
135 something similar to the ``chain rule'' of the calculus derivative: |
108 \begin{lemma} |
136 \begin{lemma} |
109 \[ |
137 \[ |
110 \Der \; c \; (A @ B) = |
138 \Der \; c \; (A @ B) = |
111 \begin{cases} |
139 \begin{cases} |
112 ((\Der \; c \; A) \, @ \, B ) \cup (\Der \; c\; B) , & \text{if} \; [] \in A \\ |
140 ((\Der \; c \; A) \, @ \, B ) \cup (\Der \; c\; B) , & \text{if} \; [] \in A \\ |
196 %Recall, the language derivative acts on a set of strings |
224 %Recall, the language derivative acts on a set of strings |
197 %and essentially chops off a particular character from |
225 %and essentially chops off a particular character from |
198 %all strings in that set, Brzozowski defined a derivative operation on regular expressions |
226 %all strings in that set, Brzozowski defined a derivative operation on regular expressions |
199 %so that after derivative $L(r\backslash c)$ |
227 %so that after derivative $L(r\backslash c)$ |
200 %will look as if it was obtained by doing a language derivative on $L(r)$: |
228 %will look as if it was obtained by doing a language derivative on $L(r)$: |
201 Recall that the semantic derivative acts on a set of |
229 Recall that the semantic derivative acts on a |
202 strings. Brzozowski noticed that this operation |
230 language (set of strings). |
|
231 One can decide whether a string $s$ belongs |
|
232 to a language $S$ by taking derivative with respect to |
|
233 that string and then checking whether the empty |
|
234 string is in the derivative: |
|
235 \begin{center} |
|
236 \parskip \baselineskip |
|
237 \def\myupbracefill#1{\rotatebox{90}{\stretchto{\{}{#1}}} |
|
238 \def\rlwd{.5pt} |
|
239 \newcommand\notate[3]{% |
|
240 \unskip\def\useanchorwidth{T}% |
|
241 \setbox0=\hbox{#1}% |
|
242 \def\stackalignment{c}\stackunder[-6pt]{% |
|
243 \def\stackalignment{c}\stackunder[-1.5pt]{% |
|
244 \stackunder[-2pt]{\strut #1}{\myupbracefill{\wd0}}}{% |
|
245 \rule{\rlwd}{#2\baselineskip}}}{% |
|
246 \strut\kern7pt$\hookrightarrow$\rlap{ \footnotesize#3}}\ignorespaces% |
|
247 } |
|
248 \Longstack{ |
|
249 \notate{$\{ \ldots ,\;$ |
|
250 \notate{s}{1}{$(c_1 :: s_1)$} |
|
251 $, \; \ldots \}$ |
|
252 }{1}{$S_{start}$} |
|
253 } |
|
254 \Longstack{ |
|
255 $\stackrel{\backslash c_1}{\longrightarrow}$ |
|
256 } |
|
257 \Longstack{ |
|
258 $\{ \ldots,\;$ \notate{$s_1$}{1}{$(c_2::s_2)$} |
|
259 $,\; \ldots \}$ |
|
260 } |
|
261 \Longstack{ |
|
262 $\stackrel{\backslash c_2}{\longrightarrow}$ |
|
263 } |
|
264 \Longstack{ |
|
265 $\{ \ldots,\; s_2 |
|
266 ,\; \ldots \}$ |
|
267 } |
|
268 \Longstack{ |
|
269 $ \xdashrightarrow{\backslash c_3\ldots\ldots} $ |
|
270 } |
|
271 \Longstack{ |
|
272 \notate{$\{\ldots, [], \ldots\}$}{1}{$S_{end} = |
|
273 S_{start}\backslash s$} |
|
274 } |
|
275 \end{center} |
|
276 \begin{center} |
|
277 $s \in S_{start} \iff [] \in S_{end}$ |
|
278 \end{center} |
|
279 \noindent |
|
280 Brzozowski noticed that this operation |
203 can be ``mirrored" on regular expressions which |
281 can be ``mirrored" on regular expressions which |
204 he calls the derivative of a regular expression $r$ |
282 he calls the derivative of a regular expression $r$ |
205 with respect to a character $c$, written |
283 with respect to a character $c$, written |
206 $r \backslash c$. |
284 $r \backslash c$. This infix operator |
207 He defined this operation such that the following property holds: |
285 takes an original regular expression $r$ as input |
|
286 and a character as a right operand and |
|
287 outputs a result, which is a new regular expression. |
|
288 The derivative operation on regular expression |
|
289 is defined such that the language of the derivative result |
|
290 coincides with the language of the original |
|
291 regular expression's language being taken the language |
|
292 derivative with respect to the same character: |
|
293 \begin{center} |
|
294 \parskip \baselineskip |
|
295 \def\myupbracefill#1{\rotatebox{90}{\stretchto{\{}{#1}}} |
|
296 \def\rlwd{.5pt} |
|
297 \newcommand\notate[3]{% |
|
298 \unskip\def\useanchorwidth{T}% |
|
299 \setbox0=\hbox{#1}% |
|
300 \def\stackalignment{c}\stackunder[-6pt]{% |
|
301 \def\stackalignment{c}\stackunder[-1.5pt]{% |
|
302 \stackunder[-2pt]{\strut #1}{\myupbracefill{\wd0}}}{% |
|
303 \rule{\rlwd}{#2\baselineskip}}}{% |
|
304 \strut\kern8pt$\hookrightarrow$\rlap{ \footnotesize#3}}\ignorespaces% |
|
305 } |
|
306 \Longstack{ |
|
307 \notate{$r$}{1}{$L \; r = \{\ldots, \;c::s_1, |
|
308 \;\ldots\}$} |
|
309 } |
|
310 \Longstack{ |
|
311 $\stackrel{\backslash c}{\longrightarrow}$ |
|
312 } |
|
313 \Longstack{ |
|
314 \notate{$r\backslash c$}{2}{$L \; (r\backslash c)= |
|
315 \{\ldots,\;s_1,\;\ldots\}$} |
|
316 } |
|
317 \end{center} |
208 \begin{center} |
318 \begin{center} |
209 |
319 |
210 \[ |
320 \[ |
211 L(r \backslash c) = \Der \; c \; L(r) |
321 L(r \backslash c) = \Der \; c \; L(r) |
212 \] |
322 \] |
213 \end{center} |
323 \end{center} |
214 \noindent |
324 \noindent |
|
325 where we do derivatives on the regular expression |
|
326 $r$ and test membership of $s$ by checking |
|
327 whether the empty string is in the language of |
|
328 $r\backslash s$. |
215 For example in the sequence case we have |
329 For example in the sequence case we have |
216 \begin{center} |
330 \begin{center} |
217 \begin{tabular}{lcl} |
331 \begin{tabular}{lcl} |
218 $\Der \; c \; (A @ B)$ & $\dn$ & |
332 $\Der \; c \; (A @ B)$ & $\dn$ & |
219 $ \textit{if} \;\, [] \in A \; |
333 $ \textit{if} \;\, [] \in A \; |