handouts/ho03.tex
changeset 662 8da26d4c2ca8
parent 578 6e5e3adc9eb1
child 667 412556272333
--- a/handouts/ho03.tex	Thu Oct 17 13:41:30 2019 +0100
+++ b/handouts/ho03.tex	Thu Oct 17 14:02:59 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
 \documentclass{article}
 \usepackage{../style}
 \usepackage{../langs}
@@ -914,24 +915,23 @@
 Page~\pageref{dfa}).\bigskip
 
 \noindent
-To start remember that we did not bother with defining and
-implementing $\epsilon$NFAs: we immediately translated them into
-equivalent NFAs. Equivalent in the sense of accepting the same
-language (though we only claimed this and did not prove it
-rigorously). Remember also that NFAs have non-deterministic
-transitions defined as a relation or implemented as function returning
-sets of states.  This non-determinism is crucial for the Thompson
-Construction to work (recall the cases for $\cdot$, $+$ and
-${}^*$). But this non-determinism makes it harder with NFAs to decide
-when a string is accepted or not; whereas such a decision is rather
-straightforward with DFAs: recall their transition function is a
-\emph{function} that returns a single state. So with DFAs we do not
-have to search at all.  What is perhaps interesting is the fact that
-for every NFA we can find a DFA that also recognises the same
-language. This might sound a bit paradoxical: NFA $\rightarrow$
-decision of acceptance hard; DFA $\rightarrow$ decision easy. But this
-\emph{is} true\ldots but of course there is always a caveat---nothing
-ever is for free in life.
+To start, remember that we did not bother with defining and implementing
+$\epsilon$NFAs: we immediately translated them into equivalent NFAs.
+Equivalent in the sense of accepting the same language (though we only
+claimed this and did not prove it rigorously). Remember also that NFAs
+have non-deterministic transitions defined as a relation, or
+alternatively my Scala implementation used transition functions returning sets of
+states.  This non-determinism is crucial for the Thompson Construction
+to work (recall the cases for $\cdot$, $+$ and ${}^*$). But this
+non-determinism makes it harder with NFAs to decide when a string is
+accepted or not; whereas such a decision is rather straightforward with
+DFAs: recall their transition function is a ``real'' function that returns
+a single state. So with DFAs we do not have to search at all.  What is
+perhaps interesting is the fact that for every NFA we can find a DFA
+that also recognises the same language. This might sound a bit
+paradoxical: NFA $\rightarrow$ decision of acceptance hard; DFA
+$\rightarrow$ decision easy. But this \emph{is} true\ldots but of course
+there is always a caveat---nothing ever is for free in life.
 
 There are actually a number of methods for transforming a NFA into
 an equivalent DFA, but the most famous one is the \emph{subset