diff -r 135fc1eba66a -r 8da26d4c2ca8 handouts/ho03.tex --- 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