--- a/progs/nfa.scala	Tue Apr 25 12:33:16 2017 +0100
+++ b/progs/nfa.scala	Fri Apr 28 11:01:25 2017 +0100
@@ -2,6 +2,16 @@
 // sets of states)
 import scala.util.Try
 
+// states class
+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
+
+
+
 // type abbreviation for partial functions
 type :=>[A, B] = PartialFunction[A, B]
 
@@ -11,9 +21,9 @@
 
 
 // NFAs
-case class NFA[A, C](starts: Set[A],            // starting states
-                     delta: (A, C) :=> Set[A],  // transition function
-                     fins:  A => Boolean) {     // final states 
+case class NFA[A, C](starts: Set[A],           // starting states
+                     delta: (A, C) :=> Set[A], // transition function
+                     fins:  A => Boolean) {    // final states 
 
   // given a state and a character, what is the set of 
   // next states? if there is none => empty set
@@ -33,4 +43,39 @@
   // is a string accepted by an NFA?
   def accepts(s: List[C]) : Boolean = 
     deltas(starts, s).exists(fins)
+
+  // depth-first version of accepts
+  def search(q: A, s: List[C]) : Boolean = s match {
+    case Nil => fins(q)
+    case c::cs => next(q, c).exists(search(_, cs))
+  }
+
+  def accepts2(s: List[C]) : Boolean =
+    starts.exists(search(_, s))
 }
+
+
+
+// NFA examples
+
+val nfa_trans1 : (State, Char) :=> Set[State] = 
+  { case (Q0, 'a') => Set(Q0, Q1) 
+    case (Q0, 'b') => Set(Q2) 
+    case (Q1, 'a') => Set(Q1) 
+    case (Q2, 'b') => Set(Q2) }
+
+val nfa1 = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2))
+
+nfa1.accepts("aa".toList)             // false
+nfa1.accepts("aaaaa".toList)          // false
+nfa1.accepts("aaaaab".toList)         // true
+nfa1.accepts("aaaaabbb".toList)       // true
+nfa1.accepts("aaaaabbbaaa".toList)    // false
+nfa1.accepts("ac".toList)             // false
+
+nfa1.accepts2("aa".toList)             // false
+nfa1.accepts2("aaaaa".toList)          // false
+nfa1.accepts2("aaaaab".toList)         // true
+nfa1.accepts2("aaaaabbb".toList)       // true
+nfa1.accepts2("aaaaabbbaaa".toList)    // false
+nfa1.accepts2("ac".toList)             // false