// NFAs in Scala using partial functions (returning// sets of states)//// load dfasimport $file.dfa, dfa._ // return an empty set, when a parial function is not definedimport scala.util.Trydef applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = Try(f(x)).getOrElse(Set[B]())// NFAscase class NFA[A, C](starts: Set[A], // the starting states delta: (A, C) :=> Set[A], // the transition function fins: A => Boolean) { // the final states // given a state and a character, what is the set of // next states? if there is none => empty set def next(q: A, c: C) : Set[A] = applyOrElse(delta, (q, c)) def nexts(qs: Set[A], c: C) : Set[A] = qs.flatMap(next(_, c)) // given some states and a string, what is the set // of next states? def deltas(qs: Set[A], s: List[C]) : Set[A] = s match { case Nil => qs case c::cs => deltas(nexts(qs, c), cs) } // 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 examplesval 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))println(nfa1.accepts("aa".toList)) // falseprintln(nfa1.accepts("aaaaa".toList)) // falseprintln(nfa1.accepts("aaaaab".toList)) // trueprintln(nfa1.accepts("aaaaabbb".toList)) // trueprintln(nfa1.accepts("aaaaabbbaaa".toList)) // falseprintln(nfa1.accepts("ac".toList)) // falseprintln(nfa1.accepts2("aa".toList)) // falseprintln(nfa1.accepts2("aaaaa".toList)) // falseprintln(nfa1.accepts2("aaaaab".toList)) // trueprintln(nfa1.accepts2("aaaaabbb".toList)) // trueprintln(nfa1.accepts2("aaaaabbbaaa".toList)) // falseprintln(nfa1.accepts2("ac".toList)) // false// subset constructionsdef subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { DFA(nfa.starts, { case (qs, c) => nfa.nexts(qs, c) }, _.exists(nfa.fins))}println(subset(nfa1).accepts("aa".toList)) // falseprintln(subset(nfa1).accepts("aaaaa".toList)) // falseprintln(subset(nfa1).accepts("aaaaab".toList)) // trueprintln(subset(nfa1).accepts("aaaaabbb".toList)) // trueprintln(subset(nfa1).accepts("aaaaabbbaaa".toList)) // falseprintln(subset(nfa1).accepts("ac".toList)) // false