# HG changeset patch # User Christian Urban # Date 1574427793 0 # Node ID 7c7854feccb5c6320baa254a69bb4903d1054904 # Parent 370508e4d7f677214611630bc80dca3f4e092014 updated diff -r 370508e4d7f6 -r 7c7854feccb5 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 370508e4d7f6 -r 7c7854feccb5 handouts/ho03.tex --- a/handouts/ho03.tex Thu Nov 21 14:41:53 2019 +0000 +++ b/handouts/ho03.tex Fri Nov 22 13:03:13 2019 +0000 @@ -1063,7 +1063,7 @@ \noindent To conclude this section, how conveniently we can implement the subset construction with our versions of NFAs and -DFAs? Very conveninetly. The code is just: +DFAs? Very conveniently. The code is just: {\small\begin{lstlisting}[language=Scala] def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { @@ -1273,7 +1273,7 @@ $\epsilon$NFA, then translate it into a NFA by removing all $\epsilon$-transitions, and then via the subset construction obtain a DFA. In all steps we made sure the language, or which strings can be -recognised, stays the same. Of couse we should have proved this in +recognised, stays the same. Of cause we should have proved this in each step, but let us cut corners here. After the last section, we can even minimise the DFA (maybe not in code). But again we made sure the same language is recognised. You might be wondering: Can we go @@ -1345,9 +1345,9 @@ Q_2 & = & Q_0\,a\,a + Q_2\,a \end{eqnarray} -\noindent where in Equation (4) we have two occurrences +\noindent where in Equation (6) we have two occurrences of $Q_0$. Like the laws about $+$ and $\cdot$, we can simplify -Equation (4) to obtain the following two equations: +Equation (6) to obtain the following two equations: \begin{eqnarray} Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\ @@ -1468,7 +1468,7 @@ automaton that recognises all its strings. \end{quote} -\noindent Note that this is not a stement for a particular language +\noindent Note that this is not a statement for a particular language (that is a particular set of strings), but about a large class of languages, namely the regular ones.