--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/dfa.scala	Wed Oct 16 02:07:02 2013 +0100
@@ -0,0 +1,64 @@
+// DFAs
+import scala.util._
+
+abstract class State
+type States = Set[State]
+
+case class IntState(i: Int) extends State
+
+object NewState {
+  var counter = 0
+  
+  def apply() : IntState = {
+    counter += 1;
+    new IntState(counter - 1)
+  }
+}
+
+
+// DFA class
+case class DFA(states: States, 
+               start: State, 
+               delta: (State, Char) => State, 
+               fins: States) {
+  
+  def deltas(q: State, s: List[Char]) : State = s match {
+    case Nil => q
+    case c::cs => deltas(delta(q, c), cs) 
+  }
+  
+  // wether a string is accepted by the automaton or not
+  def accepts(s: String) : Boolean = 
+    Try(fins contains 
+      (deltas(start, s.toList))) getOrElse false
+}
+
+
+// example DFA from the lectures
+val Q0 = NewState()
+val Q1 = NewState()
+val Q2 = NewState()
+val Q3 = NewState()
+val Q4 = NewState()
+
+
+val delta : (State, Char) => State = {
+  case (Q0, 'a') => Q1
+  case (Q0, 'b') => Q2
+  case (Q1, 'a') => Q4
+  case (Q1, 'b') => Q2
+  case (Q2, 'a') => Q3
+  case (Q2, 'b') => Q2
+  case (Q3, 'a') => Q4
+  case (Q3, 'b') => Q0
+  case (Q4, 'a') => Q4
+  case (Q4, 'b') => Q4
+}
+
+val DFA1 = DFA(Set(Q0, Q1, Q2, Q3, Q4), Q0, delta, Set(Q4))
+
+println(DFA1.accepts("aaa"))
+println(DFA1.accepts("bb"))
+println(DFA1.accepts("aaac"))
+
+