--- 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.