diff -r 564b4baec85e -r 4fc05d4f0e01 progs/automata.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/automata.scala	Fri Mar 10 23:01:17 2017 +0000
@@ -0,0 +1,197 @@
+// NFAs and DFAs based on Scala's partial functions
+
+
+// (1) Write a polymorphic function that tests whether the 
+// intersection of two sets is non-empty
+
+def share[A](a: Set[A], b: Set[A]) : Boolean = ...
+
+
+share(Set(1,2,3), Set(2, 3, 4))   // true
+share(Set(1,2,3), Set(4, 5, 6))   // false
+
+
+// State nodes of the DFAs and NFAs
+abstract class State
+type States = Set[State]
+
+// Some states for test cases
+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
+case object Q5 extends State
+case object Q6 extends State
+
+
+// Transitions for DFAs and NFAs
+type Trans = PartialFunction[(State, Char), State]
+type NTrans = Set[Trans]
+
+
+// example transition of an DFA
+val dtrans : Trans = 
+  { case (Q0, 'a') => Q1 
+    case (Q0, 'b') => Q0
+    case (Q1, 'a') => Q2 
+    case (Q1, 'b') => Q0
+    case (Q2, 'a') => Q2 
+    case (Q2, 'b') => Q0 
+  }
+
+
+// (2) Write a function that takes a transition and a 
+// (state, character)-pair as arguments and produces an 
+// optional state (the state specified by the partial transition
+// function whenever it is defined; if the transition function 
+// is undefined, return None.
+
+def fire(e: Trans, qc: (State, Char)) : Option[State] = ...
+
+
+// (3) Write a function that takes a transition, a state 
+// and a list of characters as arguments and produces 
+// the state generated by following the transitions for 
+// each character in the list.
+
+def nexts(trans: Trans, q: State, s: List[Char]) : Option[State] = ...
+
+
+
+// class for DFAs
+case class DFA(start: State,      // starting state
+               trans: Trans,      // transition
+               fins:  States)     // final states
+
+// (4) Write a function that tests whether a string is accepted 
+// by an DFA or not.
+
+def accepts(dfa: DFA, s: String) : Boolean = ...
+
+
+
+// DFA examples
+ 
+val dtrans1 : Trans = 
+  { case (Q0, 'a') => Q0 
+    case (Q0, 'b') => Q1 
+  }
+
+val dfa1 = DFA(Q0, dtrans1, Set[State](Q1))
+
+accepts(dfa1, "aaab")     // true
+accepts(dfa1, "aacb")     // false
+
+
+// NFAs
+
+
+// (5) Write a function that takes a transition set, a state
+// and a character as arguments, and calculates all possible 
+// next states (returned as set).
+
+def nnext(trans: NTrans, q: State, c: Char) : States = ...
+
+
+// (6) Write a function that takes a transition set, a set of states 
+// and a character as arguments, and calculates all possible 
+// next states that can be reached from any state in the set.
+
+def nnexts(trans: NTrans, qs: States, c: Char) : States = ...
+
+
+
+// (7) Write a function that lifts nnexts from from single 
+// characters to lists of characters.
+def nnextss(trans: NTrans, qs: States, s: List[Char]) : States = ...
+
+
+// class for NFAs
+case class NFA(start: States,       // starting state
+               trans: NTrans,       // transition edges
+               fins:  States)       // final states
+
+
+// (8) Write a function that tests whether a string is 
+// accepted by an NFA or not.
+
+def naccepts(nfa: NFA, s: String) : Boolean = ...
+
+
+// (9) Write similar functions as in (7) and (8), but instead of 
+// returning states or a boolean, calculate the number of states 
+// that need to be followed in each step.
+
+def max_nextss(trans: NTrans, qs: States, s: List[Char], max: Int) : Int = ...
+
+def max_accepts(nfa: NFA, s: String) : Int = ...
+
+
+// NFA examples
+
+
+// 1 
+val trans1 : NTrans = Set(
+  { case (Q0, 'a') => Q1 },
+  { case (Q0, _)   => Q0 },
+  { case (Q1, _)   => Q2 },
+  { case (Q2, _)   => Q3 },
+  { case (Q3, _)   => Q4 },
+  { case (Q4, 'b') => Q5 },
+  { case (Q5, 'c') => Q6 }
+)
+
+val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6))
+
+naccepts(nfa1, "axaybzbc")     // true
+naccepts(nfa1, "aaaaxaybzbc")  // true
+naccepts(nfa1, "axaybzbd")     // false
+
+// the nfa has five states, which might be all 
+// active
+
+max_accepts(nfa1, "axaybzbc")     // 3 
+max_accepts(nfa1, "aaaaxaybzbc")  // 5
+max_accepts(nfa1, "axaybzbd")     // 3
+max_accepts(nfa1, "aaaaaaaaaaaaaxaybzbd")   // 5
+
+
+// 2
+val trans2 : NTrans = Set(
+  { case (Q0, 'a') => Q0 },
+  { case (Q0, 'a') => Q1 },
+  { case (Q0, 'b') => Q2 },
+  { case (Q1, 'a') => Q1 },
+  { case (Q2, 'b') => Q2 }
+)
+
+val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2))
+
+naccepts(nfa2, "aa")             // false
+naccepts(nfa2, "aaaaa")          // false
+naccepts(nfa2, "aaaaab")         // true
+naccepts(nfa2, "aaaaabbb")       // true
+naccepts(nfa2, "aaaaabbbaaa")    // false
+naccepts(nfa2, "ac")             // false
+
+// 3
+val trans3 : NTrans = Set(
+  { case (Q0, _)   => Q0 },
+  { case (Q0, 'a') => Q1 },
+  { case (Q0, 'b') => Q3 },
+  { case (Q1, 'b') => Q2 },
+  { case (Q2, 'c') => Q5 },
+  { case (Q3, 'c') => Q4 },
+  { case (Q4, 'd') => Q5 }
+)
+
+val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5))
+
+naccepts(nfa3, "aaaaabc")      // true
+naccepts(nfa3, "aaaabcd")      // true
+naccepts(nfa3, "aaaaab")       // false
+naccepts(nfa3, "aaaabc")       // true
+naccepts(nfa3, "aaaaabbbaaa")  // false
+
+