# HG changeset patch # User Christian Urban # Date 1696154252 -3600 # Node ID 5678414a38984a1e92d9bc11bc76f18a268788b8 # Parent 14a6adca16b8ba0200d367eb21fda0c9a3c5c787 updated diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho02.tex --- a/handouts/ho02.tex Sun Oct 01 09:46:44 2023 +0100 +++ b/handouts/ho02.tex Sun Oct 01 10:57:32 2023 +0100 @@ -44,7 +44,7 @@ expressions of the form $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and corresponding strings composed of $n$ \pcode{a}s (this time the regular expressions match the strings). To see the substantial differences in the left and -right plots below, note the different scales of the $x$-axes. +right plots below, note the different scales of the $x$-axis. \begin{center} diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho03.tex --- a/handouts/ho03.tex Sun Oct 01 09:46:44 2023 +0100 +++ b/handouts/ho03.tex Sun Oct 01 10:57:32 2023 +0100 @@ -538,7 +538,7 @@ \noindent I let you think whether the NFAs can match exactly those strings the regular expressions can match. To do this translation in code we need -a way to construct states ``programatically''...and as an additional +a way to construct states ``programmatically''...and as an additional constraint Scala needs to recognise that these states are being distinct. For this I implemented in Figure~\ref{thompson1} a class \texttt{TState} that includes a counter and a companion object that @@ -1302,7 +1302,7 @@ $\epsilon$NFA, then translate it into a NFA by removing all $\epsilon$-transitions, and then via the subset construction obtain a DFA. In all steps we made sure the language, or which strings can be -recognised, stays the same. Of cause we should have proved this in +recognised, stays the same. Of couse we should have proved this in each step, but let us cut corners here. After the last section, we can even minimise the DFA (maybe not in code). But again we made sure the same language is recognised. You might be wondering: Can we go @@ -1449,7 +1449,7 @@ \] \noindent You can somewhat crosscheck your solution by taking a string -the regular expression can match and and see whether it can be matched +the regular expression can match and see whether it can be matched by the DFA. One string for example is $aaa$ and \emph{voila} this string is also matched by the automaton. diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho07.pdf Binary file handouts/ho07.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 handouts/ho10.pdf Binary file handouts/ho10.pdf has changed diff -r 14a6adca16b8 -r 5678414a3898 progs/automata/thompson.sc --- a/progs/automata/thompson.sc Sun Oct 01 09:46:44 2023 +0100 +++ b/progs/automata/thompson.sc Sun Oct 01 10:57:32 2023 +0100 @@ -47,7 +47,7 @@ // for composing an eNFA transition with an NFA transition // | is for set union -implicit def nfaOps(f: eNFAtrans) = new { +extension (f: eNFAtrans) { def +++(g: NFAtrans) : eNFAtrans = { case (q, None) => applyOrElse(f, (q, None)) case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) }