60 Clearly we cannot use the function $L$ directly in order to solve this problem, because in general |
60 Clearly we cannot use the function $L$ directly in order to solve this problem, because in general |
61 the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no algorithm |
61 the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no algorithm |
62 then can test exhaustively, whether a string is member of this set. |
62 then can test exhaustively, whether a string is member of this set. |
63 |
63 |
64 The algorithm we define below consists of two parts. One is the function $nullable$ which takes a |
64 The algorithm we define below consists of two parts. One is the function $nullable$ which takes a |
65 regular expression as argument and decides whether it can match the empty string. This can be easily |
65 regular expression as argument and decides whether it can match the empty string (this means it returns a |
66 defined recursively as follows: |
66 boolean). This can be easily defined recursively as follows: |
67 |
67 |
|
68 \begin{center} |
|
69 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
70 $nullable(\varnothing)$ & $\dn$ & $f\!\/alse$\\ |
|
71 $nullable(\epsilon)$ & $\dn$ & $true$\\ |
|
72 $nullable (c)$ & $\dn$ & $f\!alse$\\ |
|
73 $nullable (r_1 + r_2)$ & $\dn$ & $nullable(r_1) \vee nullable(r_2)$\\ |
|
74 $nullable (r_1 \cdot r_2)$ & $\dn$ & $nullable(r_1) \wedge nullable(r_2)$\\ |
|
75 $nullable (r^*)$ & $\dn$ & $true$ \\ |
|
76 \end{tabular} |
|
77 \end{center} |
|
78 |
|
79 \noindent |
|
80 The idea behind this function is that the following property holds: |
|
81 |
|
82 \[ |
|
83 nullable(r) \;\;\text{if and only if}\;\; ""\in L(r) |
|
84 \] |
|
85 |
|
86 \noindent |
|
87 On the left-hand side we have a function we can implement; on the right we have its specification. |
|
88 |
|
89 The other function is calculating a \emph{derivative} of a regular expression. This is a function |
|
90 which will take a regular expression, say $r$, and a character, say $c$, as argument and return |
|
91 a new regular expression. Beware that the intuition behind this function is not so easy to grasp on first |
|
92 reading. Essentially this function solves the following problem: if $r$ can match a string of the form |
|
93 $c\!::\!s$, what does the regular expression look like that can match just $s$. |
68 |
94 |
69 \end{document} |
95 \end{document} |
70 |
96 |
71 %%% Local Variables: |
97 %%% Local Variables: |
72 %%% mode: latex |
98 %%% mode: latex |