--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/automata/der.sc Mon Oct 19 17:50:11 2020 +0100
@@ -0,0 +1,50 @@
+// Another automaton construction
+//================================
+
+import $file.dfa, dfa._
+
+// regular expressions
+abstract class Rexp
+case object ZERO extends Rexp // matches nothing
+case object ONE extends Rexp // matches the empty string
+case class CHAR(c: Char) extends Rexp // matches a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
+case class STAR(r: Rexp) extends Rexp // star
+
+// the nullable function: tests whether the regular
+// expression can recognise the empty string
+def nullable (r: Rexp) : Boolean = r match {
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALT(r1, r2) => nullable(r1) || nullable(r2)
+ case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ case STAR(_) => true
+}
+
+// the derivative of a regular expression w.r.t. a character
+def der (c: Char, r: Rexp) : Rexp = r match {
+ case ZERO => ZERO
+ case ONE => ZERO
+ case CHAR(d) => if (c == d) ONE else ZERO
+ case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+ case SEQ(r1, r2) =>
+ if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+ else SEQ(der(c, r1), r2)
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
+}
+
+
+def flaw(r: Rexp) : DFA[Rexp, Char] = {
+ DFA(r,
+ { case (r, c) => der(c, r) },
+ nullable(_))
+}
+
+val r = STAR(CHAR('a'))
+val pseudo = flaw(r)
+println(pseudo.accepts("".toList)) // true
+println(pseudo.accepts("a".toList)) // true
+println(pseudo.accepts("aa".toList)) // true
+println(pseudo.accepts("bb".toList)) // false
--- a/progs/automata/thompson.sc Mon Oct 19 14:17:18 2020 +0100
+++ b/progs/automata/thompson.sc Mon Oct 19 17:50:11 2020 +0100
@@ -185,3 +185,8 @@
for (i <- 1 to 100 by 5) {
println(i + " " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i))))
}
+
+
+
+
+
Binary file slides/slides03.pdf has changed
--- a/slides/slides03.tex Mon Oct 19 14:17:18 2020 +0100
+++ b/slides/slides03.tex Mon Oct 19 17:50:11 2020 +0100
@@ -1492,111 +1492,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[scale=2,>=stealth',very thick,
- every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
- \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
- \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
- \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
- \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
- \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};
- \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
- (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
- (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
- (q1) edge node[above] {\alert{$a$}} (q2)
- (q2) edge [loop right] node {\alert{$a$}} ()
- (q0) edge [loop below] node {\alert{$b$}} ()
- ;
-\end{tikzpicture}
-\end{center}\bigskip
-
-\begin{center}
-\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
-\end{tabular}
-\end{center}
-
-
-Arden's Lemma:
-\begin{center}
-If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
-\end{center}
-
-\only<2-6>{\small
-\begin{textblock}{6}(1,0.8)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
-\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<3-6>{\small
-\begin{textblock}{6}(2,4.15)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
-\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<4-6>{\small
-\begin{textblock}{6}(3,7.55)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
- \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<5-6>{\small
-\begin{textblock}{6}(4,10.9)
-\begin{bubble}[7.5cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
- \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<6>{\small
-\begin{textblock}{6}(5,13.4)
-\begin{bubble}[7.5cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
- \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-
-\only<7->{\small
-\begin{textblock}{6}(6,11.5)
-\begin{bubble}[6.7cm]
-\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
-\multicolumn{3}{@{}l}{Finally:}\\
-\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
-\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\
-\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regexps and Automata}