handouts/ho03.tex
changeset 874 ffe02fd574a5
parent 764 6718ef6143b8
child 926 42ecc3186944
--- 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.