# HG changeset patch # User Christian Urban # Date 1661754419 -7200 # Node ID ffe02fd574a5a9e4709a2a97a989421dc07016b1 # Parent a25da86f7c8c367f5f2327b7fd0fbf5d8a970aa6 updated diff -r a25da86f7c8c -r ffe02fd574a5 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r a25da86f7c8c -r ffe02fd574a5 handouts/ho02.tex --- a/handouts/ho02.tex Mon Aug 29 01:16:32 2022 +0200 +++ b/handouts/ho02.tex Mon Aug 29 08:26:59 2022 +0200 @@ -8,7 +8,7 @@ \begin{document} \fnote{\copyright{} Christian Urban, King's College London, - 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021} + 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022} \section*{Handout 2 (Regular Expression Matching)} @@ -336,7 +336,7 @@ \] \noindent Note on the left-hand side of the if-and-only-if we have a -function we can implement, ofr example in Scala; on the right we have +function we can implement, for example in Scala; on the right we have its specification (which we cannot implement in a programming language). The other function of our matching algorithm calculates a @@ -518,8 +518,8 @@ \lstinputlisting[numbers=left,linebackgroundcolor= {\ifodd\value{lstnumber}\color{capri!3}\fi}] {../progs/app5.scala} -\caption{A Scala implementation of \textit{nullable} and - derivative function. These functions are easy to +\caption{A Scala implementation of the \textit{nullable} and + the derivative function. These functions are easy to implement in functional programming languages. This is because pattern matching and recursion allow us to mimic the mathematical definitions very closely. Nearly all functional diff -r a25da86f7c8c -r ffe02fd574a5 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed 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. diff -r a25da86f7c8c -r ffe02fd574a5 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r a25da86f7c8c -r ffe02fd574a5 handouts/ho04.tex --- a/handouts/ho04.tex Mon Aug 29 01:16:32 2022 +0200 +++ b/handouts/ho04.tex Mon Aug 29 08:26:59 2022 +0200 @@ -422,7 +422,7 @@ \end{center} \noindent It is a value of the right shape, namely $Stars$. It injected -$c$ into the first-value, which is in fact the value where we need to +$c$ into the first-value, which is in fact the value where we need in order to undo the derivative. Remember again the shape of the derivative of $r^*$. In place where we chopped off the $c$, we now need to do the $\inj$ of $c$. Therefore $\inj\,r\,c\,v$ in the definition above. That is the same with @@ -747,7 +747,7 @@ $r$ with respect to $c$; simplify the resulting regular expression. We continue lexing with the simplified regular expression and the string $s$. Whatever will be returned as -value, we sill need to rectify using the $f_{rect}$ from the +value, we still need to rectify using the $f_{rect}$ from the simplification and finally inject $c$ back into the (rectified) value.