# HG changeset patch # User Christian Urban # Date 1603126211 -3600 # Node ID 7dac4492b0e6e24c74206618459e83fada31c541 # Parent 06cbaaad3ba886f5aa1d8298832792c27e7e3b3b updated diff -r 06cbaaad3ba8 -r 7dac4492b0e6 progs/automata/der.sc --- /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 diff -r 06cbaaad3ba8 -r 7dac4492b0e6 progs/automata/thompson.sc --- 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)))) } + + + + + diff -r 06cbaaad3ba8 -r 7dac4492b0e6 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 06cbaaad3ba8 -r 7dac4492b0e6 slides/slides03.tex --- 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}