129 all strings accepted by a deterministic finite automaton.

   129 all strings accepted by a deterministic finite automaton.

   130 

   130 

   131 \begin{figure}[p]

   131 \begin{figure}[p]

   132 \small

   132 \small

   133 \lstinputlisting[numbers=left]{../progs/display/dfa.scala}

   133 \lstinputlisting[numbers=left]{../progs/display/dfa.scala}

   135   Note some subtleties: \texttt{deltas} implements the delta-hat

   135   Note some subtleties: \texttt{deltas} implements the delta-hat

   136   construction by lifting the (partial) transition  function to lists

   136   construction by lifting the (partial) transition  function to lists

   137   of characters. Since \texttt{delta} is given as a partial function,

   137   of characters. Since \texttt{delta} is given as a partial function,

   138   it can obviously go ``wrong'' in which case the \texttt{Try} in

   138   it can obviously go ``wrong'' in which case the \texttt{Try} in

   139   \texttt{accepts} catches the error and returns \texttt{false}---that

   139   \texttt{accepts} catches the error and returns \texttt{false}---that

   158 The DFA-class has also an argument for specifying final states. In the

   158 The DFA-class has also an argument for specifying final states. In the

   159 implementation it is not a set of states, as in the mathematical

   159 implementation it is not a set of states, as in the mathematical

   160 definition, but a function from states to booleans (this function is

   160 definition, but a function from states to booleans (this function is

   161 supposed to return true whenever a state is final; false

   161 supposed to return true whenever a state is final; false

   162 otherwise). While this boolean function is different from the sets of

   162 otherwise). While this boolean function is different from the sets of

   164 the DFA is initialised). Again it will become clear later on why I use

   164 the DFA is initialised). Again it will become clear later on why I use

   165 functions for final states, rather than sets.

   165 functions for final states, rather than sets.

   166 

   166 

   167 The most important point in the implementation is that I use Scala's

   167 The most important point in the implementation is that I use Scala's

   168 partial functions for representing the transitions; alternatives would

   168 partial functions for representing the transitions; alternatives would

   189 graph notation. Also, I suggest you to tinker with the Scala code in

   189 graph notation. Also, I suggest you to tinker with the Scala code in

   190 order to define the DFA that does not accept any string at all. 

   190 order to define the DFA that does not accept any string at all. 

   191 

   191 

   192 Finally, I let you ponder whether this is a good implementation of

   192 Finally, I let you ponder whether this is a good implementation of

   193 DFAs or not. In doing so I hope you notice that the $\varSigma$ and

   193 DFAs or not. In doing so I hope you notice that the $\varSigma$ and

   195 respectively) are missing from the class definition. This means that

   195 respectively) are missing from the class definition. This means that

   197 meant to do with DFAs. Which fishy things could that be?

   197 meant to do with DFAs. Which fishy things could that be?

   198 

   198 

   199 

   199 

   200 

   200 

   201 \subsection*{Non-Deterministic Finite Automata}

   201 \subsection*{Non-Deterministic Finite Automata}