1344 \[ |
1344 \[ |
1345 L \; (r \backslash c) = \Der \; c \; (L \; r) |
1345 L \; (r \backslash c) = \Der \; c \; (L \; r) |
1346 \] |
1346 \] |
1347 \end{property} |
1347 \end{property} |
1348 \noindent |
1348 \noindent |
1349 Pictorially, this looks as follows:\\ |
|
1350 \vspace{3mm} |
|
1351 |
|
1352 \parskip \baselineskip |
|
1353 \def\myupbracefill#1{\rotatebox{90}{\stretchto{\{}{#1}}} |
|
1354 \def\rlwd{.5pt} |
|
1355 \newcommand\notate[3]{% |
|
1356 \unskip\def\useanchorwidth{T}% |
|
1357 \setbox0=\hbox{#1}% |
|
1358 \def\stackalignment{c}\stackunder[-6pt]{% |
|
1359 \def\stackalignment{c}\stackunder[-1.5pt]{% |
|
1360 \stackunder[-2pt]{\strut #1}{\myupbracefill{\wd0}}}{% |
|
1361 \rule{\rlwd}{#2\baselineskip}}}{% |
|
1362 \strut\kern8pt$\hookrightarrow$\rlap{ \footnotesize#3}}\ignorespaces% |
|
1363 } |
|
1364 \Longstack{ |
|
1365 \notate{$r$}{1}{$L \; r = \{\ldots, \;c::s_1, |
|
1366 \;\ldots\}$} |
|
1367 } |
|
1368 \Longstack{ |
|
1369 $\stackrel{\backslash c}{\xrightarrow{\hspace*{8cm}}}$ |
|
1370 } |
|
1371 \Longstack{ |
|
1372 \notate{$r\backslash c$}{1}{$L \; (r\backslash c)= |
|
1373 \{\ldots,\;s_1,\;\ldots\}$} |
|
1374 }\\ |
|
1375 \vspace{ 3mm } |
|
1376 |
|
1377 The derivatives on regular expression can again be |
|
1378 generalised to strings. |
|
1379 One could compute $r_{start} \backslash s$ and test membership of $s$ |
|
1380 in $L \; r_{start}$ by checking |
|
1381 whether the empty string is in the language of |
|
1382 $r_{end}$ (that is $r_{start}\backslash s$).\\ |
|
1383 |
|
1384 \vspace{2mm} |
|
1385 \Longstack{ |
|
1386 \notate{$r_{start}$}{4}{ |
|
1387 \Longstack{$L \; r_{start} = \{\ldots, \;$ |
|
1388 \notate{$s$}{1}{$c_1::s_1$} |
|
1389 $, \ldots\} $ |
|
1390 } |
|
1391 } |
|
1392 } |
|
1393 \Longstack{ |
|
1394 $\stackrel{\backslash c_1}{ \xrightarrow{\hspace*{1.8cm}} }$ |
|
1395 } |
|
1396 \Longstack{ |
|
1397 \notate{$r_1$}{3}{ |
|
1398 $r_1 = r_{start}\backslash c_1$, |
|
1399 $L \; r_1 = $ |
|
1400 \Longstack{ |
|
1401 $\{ \ldots,\;$ \notate{$s_1$}{1}{$c_2::s_2$} |
|
1402 $,\; \ldots \}$ |
|
1403 } |
|
1404 } |
|
1405 } |
|
1406 \Longstack{ |
|
1407 $\stackrel{\backslash c_2}{\xrightarrow{\hspace*{1.8cm}}}$ |
|
1408 } |
|
1409 \Longstack{ |
|
1410 $r_2$ |
|
1411 } |
|
1412 \Longstack{ |
|
1413 $ \xdashrightarrow{\hspace*{0.3cm} \backslash c_3 \ldots \ldots \ldots \hspace*{0.3cm}} $ |
|
1414 } |
|
1415 \Longstack{ |
|
1416 \notate{$r_{end}$}{1}{ |
|
1417 $L \; r_{end} = \{\ldots, \; [], \ldots\}$} |
|
1418 } |
|
1419 |
|
1420 |
|
1421 We have the property that |
|
1422 \begin{property} |
|
1423 $s \in L \; r_{start} \iff [] \in L \; r_{end}$ |
|
1424 \end{property} |
|
1425 \noindent |
|
1426 Next, we give the recursive definition of derivative on |
1349 Next, we give the recursive definition of derivative on |
1427 regular expressions so that it satisfies the properties above. |
1350 regular expressions so that it satisfies the properties above. |
1428 %The derivative function, written $r\backslash c$, |
1351 %The derivative function, written $r\backslash c$, |
1429 %takes a regular expression $r$ and character $c$, and |
1352 %takes a regular expression $r$ and character $c$, and |
1430 %returns a new regular expression representing |
1353 %returns a new regular expression representing |