152 $\textit{mkeps}(r_1 \cdot r_2)$ & $\dn$ & $Seq(\textit{mkeps}(r_1),\textit{mkeps}(r_2))$\\ |
152 $\textit{mkeps}(r_1 \cdot r_2)$ & $\dn$ & $Seq(\textit{mkeps}(r_1),\textit{mkeps}(r_2))$\\ |
153 $\textit{mkeps}(r^*)$ & $\dn$ & $Stars\,[]$ \\ |
153 $\textit{mkeps}(r^*)$ & $\dn$ & $Stars\,[]$ \\ |
154 \end{tabular} |
154 \end{tabular} |
155 \end{center} |
155 \end{center} |
156 |
156 |
157 \noindent There is are no cases for $\ZERO$ and $c$, since |
157 \noindent There are no cases for $\ZERO$ and $c$, since |
158 these regular expression cannot match the empty string. Note |
158 these regular expression cannot match the empty string. Note |
159 also that in case of alternatives we give preference to the |
159 also that in case of alternatives we give preference to the |
160 regular expression on the left-hand side. This will become |
160 regular expression on the left-hand side. This will become |
161 important later on. |
161 important later on. |
162 |
162 |
238 right-alternative again. |
238 right-alternative again. |
239 |
239 |
240 Next we have to ``inject'' the last character, that is $c$ in |
240 Next we have to ``inject'' the last character, that is $c$ in |
241 the running example, into this value $v_4$ in order to |
241 the running example, into this value $v_4$ in order to |
242 calculate how $r_3$ could have matched the string $c$. |
242 calculate how $r_3$ could have matched the string $c$. |
|
243 For this we call injection with $\textit{inj}(r_3, c, v_4)$. |
243 According to the definition of $\textit{inj}$ we obtain |
244 According to the definition of $\textit{inj}$ we obtain |
244 |
245 |
245 \begin{center} |
246 \begin{center} |
246 $v_3:\;Right(Seq(Empty, Char(c)))$ |
247 $v_3:\;Right(Seq(Empty, Char(c)))$ |
247 \end{center} |
248 \end{center} |
248 |
249 |
249 \noindent This is the correct result, because $r_3$ needs |
250 \noindent This is the correct result, because $r_3$ needs |
250 to use the right-hand alternative, and then $\ONE$ needs |
251 to use the right-hand alternative, and then $\ONE$ needs |
251 to match the empty string and $c$ needs to match $c$. |
252 to match the empty string and $c$ needs to match $c$. |
252 Next we need to inject back the letter $b$ into $v_3$. This |
253 Next we need to inject back the letter $b$ into $v_3$. |
253 gives |
254 For this we call injection with $\textit{inj}(r_2, b, v_3)$. |
|
255 This gives |
254 |
256 |
255 \begin{center} |
257 \begin{center} |
256 $v_2:\;Seq(Empty, Seq(Char(b), Char(c)))$ |
258 $v_2:\;Seq(Empty, Seq(Char(b), Char(c)))$ |
257 \end{center} |
259 \end{center} |
258 |
260 |
259 \noindent which is again the correct result for how $r_2$ |
261 \noindent which is again the correct result for how $r_2$ |
260 matched the string $bc$. Finally we need to inject back the |
262 matched the string $bc$. Finally we need to inject back the |
261 letter $a$ into $v_2$ giving the final result |
263 letter $a$ into $v_2$ giving the final result. |
|
264 For this we call injection with $\textit{inj}(r_1, a, v_2)$ |
|
265 and obtain |
262 |
266 |
263 \begin{center} |
267 \begin{center} |
264 $v_1:\;Seq(Char(a), Seq(Char(b), Char(c)))$ |
268 $v_1:\;Seq(Char(a), Seq(Char(b), Char(c)))$ |
265 \end{center} |
269 \end{center} |
266 |
270 |
267 \noindent This now corresponds to how the regular |
271 \noindent This value corresponds to how the regular expression $r_1$, |
268 expression $a \cdot (b \cdot c)$ matched the string $abc$. |
272 namely $a \cdot (b \cdot c)$, matched the string $abc$. |
269 |
273 |
270 There are a few auxiliary functions that are of interest |
274 There are a few auxiliary functions that are of interest |
271 when analysing this algorithm. One is called \emph{flatten}, |
275 when analysing this algorithm. One is called \emph{flatten}, |
272 written $|\_|$, which extracts the string ``underlying'' a |
276 written $|\_|$, which extracts the string ``underlying'' a |
273 value. It is defined recursively as |
277 value. It is defined recursively as |