--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/automata_sol.scala Fri Mar 10 23:01:17 2017 +0000
@@ -0,0 +1,222 @@
+// 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 =
+ !(a intersect b).isEmpty
+
+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] =
+ e.lift.apply(qc)
+
+
+// (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] = s match {
+ case Nil => Some(q)
+ case c::cs => fire(trans, (q, c)).flatMap(nexts(trans, _, cs))
+}
+
+
+
+// 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 = nexts(dfa.trans, dfa.start, s.toList) match {
+ case None => false
+ case Some(q) => dfa.fins contains q
+}
+
+
+// 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 = {
+ trans.map(fire(_, (q, c))).flatten
+}
+
+// (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 = {
+ qs.flatMap(nnext(trans, _, c))
+}
+
+
+// (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 = s match {
+ case Nil => qs
+ case c::cs => {
+ val ns = nnexts(trans, qs, c)
+ nnextss(trans, ns, cs)
+ }
+}
+
+// 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 = {
+ share(nnextss(nfa.trans, nfa.start, s.toList), nfa.fins)
+}
+
+
+// (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 = s match {
+ case Nil => max
+ case c::cs => {
+ val ns = nnexts(trans, qs, c)
+ val ns_size = ns.size
+ if (max < ns_size) max_nextss(trans, ns, cs, ns_size)
+ else max_nextss(trans, ns, cs, max)
+ }
+}
+
+def max_accepts(nfa: NFA, s: String) : Int = {
+ max_nextss(nfa.trans, nfa.start, s.toList, 0)
+}
+
+
+// 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
+
+