handouts/ho03.tex
changeset 932 5678414a3898
parent 926 42ecc3186944
child 936 0b5f06539a84
equal deleted inserted replaced
931:14a6adca16b8 932:5678414a3898
   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