diff -r a25da86f7c8c -r ffe02fd574a5 handouts/ho03.tex --- a/handouts/ho03.tex Mon Aug 29 01:16:32 2022 +0200 +++ b/handouts/ho03.tex Mon Aug 29 08:26:59 2022 +0200 @@ -6,7 +6,7 @@ \begin{document} -\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2020} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2020, 2022} \section*{Handout 3 (Finite Automata)} @@ -1067,7 +1067,7 @@ quickly you can decide whether a string is accepted by a DFA or not. So the caveat with DFAs is that they might make the task of finding the next state trivial, but might require $2^n$ times as many -states then a NFA.\bigskip +states than a NFA.\bigskip \noindent To conclude this section, how conveniently we can @@ -1572,7 +1572,8 @@ actually do play a role of generating a DFA from a regular expression. And we can also see this in our implementation\ldots{}because there is one flaw in our representation of automata and transitions as partial -functions. We can represent automata with infinite states, which is +functions....remember I said something about fishy things. +Namely, we can represent automata with infinite states, which is actually forbidden by the definition of what an automaton is. We can exploit this flaw as follows: Suppose our alphabet consists of the characters $c_1$ to $c_n$. Then we can generate an ``automaton'' @@ -1613,11 +1614,13 @@ I let you implement this ``automaton''. While this makes all sense (modulo the flaw with the infinite states), -does this automaton teach us anything? The answer is no, because it +does this automaton teach us anything new? The answer is no, because it boils down to just another implementation of the Brzozowski -algorithm. There \emph{is} something interesting in this construction +algorithm from Lecture 2. There \emph{is} however something interesting +in this construction which Brzozowski already cleverly found out, because there is a way to restrict the number of states to something finite. +Meaning it would give us a real automaton. However, this would lead us far, far away from what we should discuss here.