917 To start remember that we did not bother with defining and

   918 To start, remember that we did not bother with defining and implementing

   918 implementing $\epsilon$NFAs: we immediately translated them into

   919 $\epsilon$NFAs: we immediately translated them into equivalent NFAs.

   919 equivalent NFAs. Equivalent in the sense of accepting the same

   920 Equivalent in the sense of accepting the same language (though we only

   920 language (though we only claimed this and did not prove it

   921 claimed this and did not prove it rigorously). Remember also that NFAs

   921 rigorously). Remember also that NFAs have non-deterministic

   922 have non-deterministic transitions defined as a relation, or

   922 transitions defined as a relation or implemented as function returning

   923 alternatively my Scala implementation used transition functions returning sets of

   923 sets of states.  This non-determinism is crucial for the Thompson

   924 states.  This non-determinism is crucial for the Thompson Construction

   924 Construction to work (recall the cases for $\cdot$, $+$ and

   925 to work (recall the cases for $\cdot$, $+$ and ${}^*$). But this

   925 ${}^*$). But this non-determinism makes it harder with NFAs to decide

   926 non-determinism makes it harder with NFAs to decide when a string is

   926 when a string is accepted or not; whereas such a decision is rather

   927 accepted or not; whereas such a decision is rather straightforward with

   927 straightforward with DFAs: recall their transition function is a

   928 DFAs: recall their transition function is a ``real'' function that returns

   928 \emph{function} that returns a single state. So with DFAs we do not

   929 a single state. So with DFAs we do not have to search at all.  What is

   929 have to search at all.  What is perhaps interesting is the fact that

   930 perhaps interesting is the fact that for every NFA we can find a DFA

   930 for every NFA we can find a DFA that also recognises the same

   931 that also recognises the same language. This might sound a bit

   931 language. This might sound a bit paradoxical: NFA $\rightarrow$

   932 paradoxical: NFA $\rightarrow$ decision of acceptance hard; DFA

   932 decision of acceptance hard; DFA $\rightarrow$ decision easy. But this

   933 $\rightarrow$ decision easy. But this \emph{is} true\ldots but of course

   933 \emph{is} true\ldots but of course there is always a caveat---nothing

   934 there is always a caveat---nothing ever is for free in life.

   934 ever is for free in life.