536 \end{equation} |
536 \end{equation} |
537 |
537 |
538 \noindent |
538 \noindent |
539 I let you think whether the NFAs can match exactly those strings the |
539 I let you think whether the NFAs can match exactly those strings the |
540 regular expressions can match. To do this translation in code we need |
540 regular expressions can match. To do this translation in code we need |
541 a way to construct states ``programatically''...and as an additional |
541 a way to construct states ``programmatically''...and as an additional |
542 constraint Scala needs to recognise that these states are being distinct. |
542 constraint Scala needs to recognise that these states are being distinct. |
543 For this I implemented in Figure~\ref{thompson1} a class |
543 For this I implemented in Figure~\ref{thompson1} a class |
544 \texttt{TState} that includes a counter and a companion object that |
544 \texttt{TState} that includes a counter and a companion object that |
545 increases this counter whenever a new state is created.\footnote{You might |
545 increases this counter whenever a new state is created.\footnote{You might |
546 have to read up what \emph{companion objects} do in Scala.} |
546 have to read up what \emph{companion objects} do in Scala.} |
1300 reflect on what you have read so far, the story is that you can take a |
1300 reflect on what you have read so far, the story is that you can take a |
1301 regular expression, translate it via the Thompson Construction into an |
1301 regular expression, translate it via the Thompson Construction into an |
1302 $\epsilon$NFA, then translate it into a NFA by removing all |
1302 $\epsilon$NFA, then translate it into a NFA by removing all |
1303 $\epsilon$-transitions, and then via the subset construction obtain a |
1303 $\epsilon$-transitions, and then via the subset construction obtain a |
1304 DFA. In all steps we made sure the language, or which strings can be |
1304 DFA. In all steps we made sure the language, or which strings can be |
1305 recognised, stays the same. Of cause we should have proved this in |
1305 recognised, stays the same. Of couse we should have proved this in |
1306 each step, but let us cut corners here. After the last section, we |
1306 each step, but let us cut corners here. After the last section, we |
1307 can even minimise the DFA (maybe not in code). But again we made sure |
1307 can even minimise the DFA (maybe not in code). But again we made sure |
1308 the same language is recognised. You might be wondering: Can we go |
1308 the same language is recognised. You might be wondering: Can we go |
1309 into the other direction? Can we go from a DFA and obtain a regular |
1309 into the other direction? Can we go from a DFA and obtain a regular |
1310 expression that can recognise the same language as the DFA?\medskip |
1310 expression that can recognise the same language as the DFA?\medskip |
1447 \[ |
1447 \[ |
1448 (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^* |
1448 (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^* |
1449 \] |
1449 \] |
1450 |
1450 |
1451 \noindent You can somewhat crosscheck your solution by taking a string |
1451 \noindent You can somewhat crosscheck your solution by taking a string |
1452 the regular expression can match and and see whether it can be matched |
1452 the regular expression can match and see whether it can be matched |
1453 by the DFA. One string for example is $aaa$ and \emph{voila} this |
1453 by the DFA. One string for example is $aaa$ and \emph{voila} this |
1454 string is also matched by the automaton. |
1454 string is also matched by the automaton. |
1455 |
1455 |
1456 We should prove that Brzozowski's method really produces an equivalent |
1456 We should prove that Brzozowski's method really produces an equivalent |
1457 regular expression. But for the purposes of this module, we omit |
1457 regular expression. But for the purposes of this module, we omit |