--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/display/dfa.scala	Fri Apr 28 11:01:25 2017 +0100
@@ -0,0 +1,43 @@
+// DFAs in Scala using partial functions
+import scala.util.Try
+
+// type abbreviation for partial functions
+type :=>[A, B] = PartialFunction[A, B]
+
+case class DFA[A, C](start: A,              // starting state
+                     delta: (A, C) :=> A,   // transition (partial fun)
+                     fins:  A => Boolean) { // final states
+
+  def deltas(q: A, s: List[C]) : A = s match {
+    case Nil => q
+    case c::cs => deltas(delta(q, c), cs)
+  }
+
+  def accepts(s: List[C]) : Boolean = 
+    Try(fins(deltas(start, s))) getOrElse false
+}
+
+// the example shown earlier in the handout 
+abstract class State
+case object Q0 extends State
+case object Q1 extends State
+case object Q2 extends State
+case object Q3 extends State
+case object Q4 extends State
+
+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 dfa = DFA(Q0, delta, Set[State](Q4))
+
+dfa.accepts("bbabaab".toList)   // true
+dfa.accepts("baba".toList)      // false