// NFAs and DFAs based on Scala's partial functions// (1) Write a polymorphic function that tests whether the // intersection of two sets is non-emptydef share[A](a: Set[A], b: Set[A]) : Boolean = ...share(Set(1,2,3), Set(2, 3, 4)) // trueshare(Set(1,2,3), Set(4, 5, 6)) // false// State nodes of the DFAs and NFAsabstract class Statetype States = Set[State]// Some states for test casescase object Q0 extends Statecase object Q1 extends Statecase object Q2 extends Statecase object Q3 extends Statecase object Q4 extends Statecase object Q5 extends Statecase object Q6 extends State// Transitions for DFAs and NFAstype Trans = PartialFunction[(State, Char), State]type NTrans = Set[Trans]// example transition of an DFAval 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 DFAscase 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 examplesval dtrans1 : Trans = { case (Q0, 'a') => Q0 case (Q0, 'b') => Q1 }val dfa1 = DFA(Q0, dtrans1, Set[State](Q1))accepts(dfa1, "aaab") // trueaccepts(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 NFAscase 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") // truenaccepts(nfa1, "aaaaxaybzbc") // truenaccepts(nfa1, "axaybzbd") // false// the nfa has five states, which might be all // activemax_accepts(nfa1, "axaybzbc") // 3 max_accepts(nfa1, "aaaaxaybzbc") // 5max_accepts(nfa1, "axaybzbd") // 3max_accepts(nfa1, "aaaaaaaaaaaaaxaybzbd") // 5// 2val 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") // falsenaccepts(nfa2, "aaaaa") // falsenaccepts(nfa2, "aaaaab") // truenaccepts(nfa2, "aaaaabbb") // truenaccepts(nfa2, "aaaaabbbaaa") // falsenaccepts(nfa2, "ac") // false// 3val 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") // truenaccepts(nfa3, "aaaabcd") // truenaccepts(nfa3, "aaaaab") // falsenaccepts(nfa3, "aaaabc") // truenaccepts(nfa3, "aaaaabbbaaa") // false