--- /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"))

Binary file hw04.pdf has changed

--- 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))$

Binary file proof.pdf has changed

--- 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: 

--- 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}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%