equal
deleted
inserted
replaced
93 of the algorithm and $mkeps/inj$, the path from right to left, |
93 of the algorithm and $mkeps/inj$, the path from right to left, |
94 the second phase. This picture shows the steps required when a |
94 the second phase. This picture shows the steps required when a |
95 regular expression, say $r_1$, matches the string $abc$. We |
95 regular expression, say $r_1$, matches the string $abc$. We |
96 first build the three derivatives (according to $a$, $b$ and |
96 first build the three derivatives (according to $a$, $b$ and |
97 $c$). We then use $nullable$ to find out whether the resulting |
97 $c$). We then use $nullable$ to find out whether the resulting |
98 regular expression can match the empty string. If yes we call |
98 regular expression can match the empty string. If yes, we call |
99 the function $mkeps$. |
99 the function $mkeps$. |
100 |
100 |
101 \begin{figure}[t] |
101 \begin{figure}[t] |
102 \begin{center} |
102 \begin{center} |
103 \begin{tikzpicture}[scale=2,node distance=1.2cm, |
103 \begin{tikzpicture}[scale=2,node distance=1.2cm, |
138 $mkeps(r_1 \cdot r_2)$ & $\dn$ & $Seq(mkeps(r_1),mkeps(r_2))$\\ |
138 $mkeps(r_1 \cdot r_2)$ & $\dn$ & $Seq(mkeps(r_1),mkeps(r_2))$\\ |
139 $mkeps(r^*)$ & $\dn$ & $[]$ \\ |
139 $mkeps(r^*)$ & $\dn$ & $[]$ \\ |
140 \end{tabular} |
140 \end{tabular} |
141 \end{center} |
141 \end{center} |
142 |
142 |
143 \noindent There are no cases for $\epsilon$ and $c$, since |
143 \noindent There are no cases for $\varnothing$ and $c$, since |
144 these regular expression cannot match the empty string. Note |
144 these regular expression cannot match the empty string. Note |
145 also that in case of alternatives we give preference to the |
145 also that in case of alternatives we give preference to the |
146 regular expression on the left-hand side. This will become |
146 regular expression on the left-hand side. This will become |
147 important later on. |
147 important later on. |
148 |
148 |
170 \end{tabular} |
170 \end{tabular} |
171 \end{center} |
171 \end{center} |
172 |
172 |
173 \noindent This definition is by recursion on the regular |
173 \noindent This definition is by recursion on the regular |
174 expression and by analysing the shape of the values. Therefore |
174 expression and by analysing the shape of the values. Therefore |
175 there are, for example, three cases for sequnece regular |
175 there are, for example, three cases for sequence regular |
176 expressions. The last clause for the star regular expression |
176 expressions. The last clause for the star regular expression |
177 returns a list where the first element is $inj\,r\,c\,v$ and |
177 returns a list where the first element is $inj\,r\,c\,v$ and |
178 the other elements are $vs$. That means $\_\,::\,\_$ should be |
178 the other elements are $vs$. That means $\_\,::\,\_$ should be |
179 read as list cons. |
179 read as list cons. |
180 |
180 |