# HG changeset patch # User Christian Urban # Date 1350254509 -3600 # Node ID eeff9953a1c18eb614692bda8daec2ff558daa68 # Parent 92b3e287d87e27e066cf83177090c9141c961e12 tuned diff -r 92b3e287d87e -r eeff9953a1c1 automata.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/automata.scala Sun Oct 14 23:41:49 2012 +0100 @@ -0,0 +1,95 @@ + +// a class for deterministic finite automata, +// the type of states is kept polymorphic + +case class Automaton[A](start: A, states: Set[A], delta: Map[(A, Char), A], fins: Set[A]) { + + // the transition function lifted to list of characters + def deltas(q: A, cs: List[Char]) : Either[A, String] = + if (states.contains(q)) cs match { + case Nil => Left(q) + case c::cs => + if (delta.isDefinedAt(q, c)) deltas(delta(q, c), cs) + else Right(q + " does not have a transition for " + c) + } + else Right(q + " is not a state of the automaton") + + // wether a string is accepted by the automaton + def accepts(s: String) = deltas(start, s.toList) match { + case Left(q) => fins.contains(q) + case _ => false + } +} + + +// translating a regular expression into a finite +// automaton + +abstract class Rexp + +case object NULL extends Rexp +case object EMPTY extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp + +implicit def string2rexp(s : String) = { + def chars2rexp (cs: List[Char]) : Rexp = cs match { + case Nil => EMPTY + case c::Nil => CHAR(c) + case c::cs => SEQ(CHAR(c), chars2rexp(cs)) + } + chars2rexp(s.toList) +} + +def nullable (r: Rexp) : Boolean = r match { + case NULL => false + case EMPTY => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true +} + +def der (r: Rexp, c: Char) : Rexp = r match { + case NULL => NULL + case EMPTY => NULL + case CHAR(d) => if (c == d) EMPTY else NULL + case ALT(r1, r2) => ALT(der(r1, c), der(r2, c)) + case SEQ(r1, r2) => if (nullable(r1)) ALT(SEQ(der(r1, c), r2), der(r2, c)) + else SEQ(der(r1, c), r2) + case STAR(r) => SEQ(der(r, c), STAR(r)) +} + + +// Here we construct an automaton whose +// states are regular expressions +type State = Rexp +type States = Set[State] +type Transition = Map[(State, Char), State] + +def goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = { + val qc : State = der(q, c) + if (qs.contains(qc)) (qs, delta + ((q, c) -> q)) + else explore(qs + qc, delta + ((q, c) -> qc), qc) +} + +// we use as an alphabet all lowercase letters +val alphabet = "abcdefghijklmnopqrstuvwxyz".toSet + +def explore (qs: States, delta: Transition, q: State) : (States, Transition) = + alphabet.foldRight[(States, Transition)] (qs, delta) ((c, qsd) => goto(q, c, qsd._1, qsd._2)) + + +def mk_automaton (r: Rexp) : Automaton[Rexp] = { + val (qs, delta) = explore(Set(r), Map(), r); + val fins = for (q <- qs if nullable(q)) yield q; + Automaton[Rexp](r, qs, delta, fins) +} + +val A = mk_automaton(ALT("ab","ac")) + +println(A.accepts("bd")) +println(A.accepts("ab")) +println(A.accepts("ac")) diff -r 92b3e287d87e -r eeff9953a1c1 hw04.pdf Binary file hw04.pdf has changed diff -r 92b3e287d87e -r eeff9953a1c1 hw04.tex --- a/hw04.tex Fri Oct 12 05:45:48 2012 +0100 +++ b/hw04.tex Sun Oct 14 23:41:49 2012 +0100 @@ -11,6 +11,9 @@ \section*{Homework 4} \begin{enumerate} +\item Why is every finite set of strings a regular language? + + \item Give an automaton that can recognise the language $L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$. @@ -18,13 +21,25 @@ string $s$. Given the following \emph{reversing} function on regular expressions +\begin{center} +\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} +$rev(\varnothing)$ & $\dn$ & $\varnothing$\\ +$rev(\epsilon)$ & $\dn$ & $\epsilon$\\ +$rev(c)$ & $\dn$ & $c$\\ +$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ +$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ +$rev(r^*)$ & $\dn$ & $rev(r)^*$\\ +\end{tabular} +\end{center} + + and the set \begin{center} $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ \end{center} -prove that +prove whether \begin{center} $L(rev(r)) = Rev (L(r))$ diff -r 92b3e287d87e -r eeff9953a1c1 proof.pdf Binary file proof.pdf has changed diff -r 92b3e287d87e -r eeff9953a1c1 proof.tex --- a/proof.tex Fri Oct 12 05:45:48 2012 +0100 +++ b/proof.tex Sun Oct 14 23:41:49 2012 +0100 @@ -105,7 +105,12 @@ $d \not=c$: We have $der\,c\,d = \varnothing$. We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \varnothing$. Hence we have $\varnothing = \varnothing$ in (c). +\end{itemize} +\noindent +These were the easy base cases. Now come the inductive cases. + +\begin{itemize} \item Fourth Case: $P(r_1 + r_2)$ is $L(der\,c\,(r_1 + r_2)) = Der\,c\,(L(r_1 + r_2))$ (d). This is what we have to show. We can assume already: @@ -169,9 +174,34 @@ Similarly in the case where $r_1$ is \emph{not} nullable. -\item Sixth Case: +\item Sixth Case: $P(r^*)$ is $L(der\,c\,(r^*)) = Der\,c\,L(r^*)$. We can assume already: + +\begin{center} +\begin{tabular}{ll} +$P(r)$: & $L(der\,c\,r) = Der\,c\,(L(r))$ (I) +\end{tabular} +\end{center} + +We have $der\,c\,(r^*) = der\,c\,r\cdot r^*$. Which means $L(der\,c\,(r^*)) = L(der\,c\,r\cdot r^*)$ and +further $L(der\,c\,r) \,@\, L(r^*)$. By induction hypothesis (I) we know that is equal to +$(Der\,c\,L(r)) \,@\, L(r^*)$. (*) + \end{itemize} + + + +Let us now analyse $Der\,c\,L(r^*)$, which is equal to $Der\,c\,((L(r))^*)$. Now $(L(r))^*$ is defined +as $\bigcup_{n \ge 0} L(r)$. We can write this as $L(r)^0 \cup \bigcup_{n \ge 1} L(r)$, where we just +separated the first union and then let the ``big-union'' start from $1$. Form this we can already infer + +\begin{center} +$Der\,c\,(L(r^*)) = Der\,c\,(L(r)^0 \cup \bigcup_{n \ge 1} L(r)) = (Der\,c\,L(r)^0) \cup Der\,c\,(\bigcup_{n \ge 1} L(r))$ +\end{center} + +The first union ``disappears'' since $Der\,c\,(L(r)^0) = \varnothing$. + + \end{document} %%% Local Variables: diff -r 92b3e287d87e -r eeff9953a1c1 slides04.tex --- a/slides04.tex Fri Oct 12 05:45:48 2012 +0100 +++ b/slides04.tex Sun Oct 14 23:41:49 2012 +0100 @@ -113,11 +113,23 @@ \item tokenization identifies lexeme in an input stream of characters (or string) and categorizes them into tokens -\item maximal munch rule +\item longest match rule (maximal munch rule): The +longest initial substring matched by any regular expression is taken +as next token. + +\item Rule priority: +For a particular longest initial substring, the first regular +expression that can match determines the token. + +\item problem with infix operations, for example i-12 \end{itemize} \url{http://www.technologyreview.com/tr10/?year=2011} +finite deterministic automata/ nondeterministic automaton + + + \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%