|
1 // NFAs and DFAs based on Scala's partial functions |
|
2 |
|
3 |
|
4 // (1) Write a polymorphic function that tests whether the |
|
5 // intersection of two sets is non-empty |
|
6 |
|
7 def share[A](a: Set[A], b: Set[A]) : Boolean = |
|
8 !(a intersect b).isEmpty |
|
9 |
|
10 share(Set(1,2,3), Set(2, 3, 4)) // true |
|
11 share(Set(1,2,3), Set(4, 5, 6)) // false |
|
12 |
|
13 |
|
14 // State nodes of the DFAs and NFAs |
|
15 abstract class State |
|
16 type States = Set[State] |
|
17 |
|
18 // Some states for test cases |
|
19 case object Q0 extends State |
|
20 case object Q1 extends State |
|
21 case object Q2 extends State |
|
22 case object Q3 extends State |
|
23 case object Q4 extends State |
|
24 case object Q5 extends State |
|
25 case object Q6 extends State |
|
26 |
|
27 |
|
28 // Transitions for DFAs and NFAs |
|
29 type Trans = PartialFunction[(State, Char), State] |
|
30 type NTrans = Set[Trans] |
|
31 |
|
32 |
|
33 // example transition of an DFA |
|
34 val dtrans : Trans = |
|
35 { case (Q0, 'a') => Q1 |
|
36 case (Q0, 'b') => Q0 |
|
37 case (Q1, 'a') => Q2 |
|
38 case (Q1, 'b') => Q0 |
|
39 case (Q2, 'a') => Q2 |
|
40 case (Q2, 'b') => Q0 |
|
41 } |
|
42 |
|
43 |
|
44 // (2) Write a function that takes a transition and a |
|
45 // (state, character)-pair as arguments and produces an |
|
46 // optional state (the state specified by the partial transition |
|
47 // function whenever it is defined; if the transition function |
|
48 // is undefined, return None. |
|
49 |
|
50 def fire(e: Trans, qc: (State, Char)) : Option[State] = |
|
51 e.lift.apply(qc) |
|
52 |
|
53 |
|
54 // (3) Write a function that takes a transition, a state |
|
55 // and a list of characters as arguments and produces |
|
56 // the state generated by following the transitions for |
|
57 // each character in the list. |
|
58 |
|
59 def nexts(trans: Trans, q: State, s: List[Char]) : Option[State] = s match { |
|
60 case Nil => Some(q) |
|
61 case c::cs => fire(trans, (q, c)).flatMap(nexts(trans, _, cs)) |
|
62 } |
|
63 |
|
64 |
|
65 |
|
66 // class for DFAs |
|
67 case class DFA(start: State, // starting state |
|
68 trans: Trans, // transition |
|
69 fins: States) // final states |
|
70 |
|
71 // (4) Write a function that tests whether a string is accepted |
|
72 // by an DFA or not. |
|
73 |
|
74 def accepts(dfa: DFA, s: String) : Boolean = nexts(dfa.trans, dfa.start, s.toList) match { |
|
75 case None => false |
|
76 case Some(q) => dfa.fins contains q |
|
77 } |
|
78 |
|
79 |
|
80 // DFA examples |
|
81 |
|
82 val dtrans1 : Trans = |
|
83 { case (Q0, 'a') => Q0 |
|
84 case (Q0, 'b') => Q1 |
|
85 } |
|
86 |
|
87 val dfa1 = DFA(Q0, dtrans1, Set[State](Q1)) |
|
88 |
|
89 accepts(dfa1, "aaab") // true |
|
90 accepts(dfa1, "aacb") // false |
|
91 |
|
92 |
|
93 // NFAs |
|
94 |
|
95 |
|
96 // (5) Write a function that takes a transition set, a state |
|
97 // and a character as arguments, and calculates all possible |
|
98 // next states (returned as set). |
|
99 |
|
100 def nnext(trans: NTrans, q: State, c: Char) : States = { |
|
101 trans.map(fire(_, (q, c))).flatten |
|
102 } |
|
103 |
|
104 // (6) Write a function that takes a transition set, a set of states |
|
105 // and a character as arguments, and calculates all possible |
|
106 // next states that can be reached from any state in the set. |
|
107 |
|
108 def nnexts(trans: NTrans, qs: States, c: Char) : States = { |
|
109 qs.flatMap(nnext(trans, _, c)) |
|
110 } |
|
111 |
|
112 |
|
113 // (7) Write a function that lifts nnexts from from single |
|
114 // characters to lists of characters. |
|
115 def nnextss(trans: NTrans, qs: States, s: List[Char]) : States = s match { |
|
116 case Nil => qs |
|
117 case c::cs => { |
|
118 val ns = nnexts(trans, qs, c) |
|
119 nnextss(trans, ns, cs) |
|
120 } |
|
121 } |
|
122 |
|
123 // class for NFAs |
|
124 case class NFA(start: States, // starting state |
|
125 trans: NTrans, // transition edges |
|
126 fins: States) // final states |
|
127 |
|
128 |
|
129 // (8) Write a function that tests whether a string is |
|
130 // accepted by an NFA or not. |
|
131 |
|
132 def naccepts(nfa: NFA, s: String) : Boolean = { |
|
133 share(nnextss(nfa.trans, nfa.start, s.toList), nfa.fins) |
|
134 } |
|
135 |
|
136 |
|
137 // (9) Write similar functions as in (7) and (8), but instead of |
|
138 // returning states or a boolean, calculate the number of states |
|
139 // that need to be followed in each step. |
|
140 |
|
141 def max_nextss(trans: NTrans, qs: States, s: List[Char], max: Int) : Int = s match { |
|
142 case Nil => max |
|
143 case c::cs => { |
|
144 val ns = nnexts(trans, qs, c) |
|
145 val ns_size = ns.size |
|
146 if (max < ns_size) max_nextss(trans, ns, cs, ns_size) |
|
147 else max_nextss(trans, ns, cs, max) |
|
148 } |
|
149 } |
|
150 |
|
151 def max_accepts(nfa: NFA, s: String) : Int = { |
|
152 max_nextss(nfa.trans, nfa.start, s.toList, 0) |
|
153 } |
|
154 |
|
155 |
|
156 // NFA examples |
|
157 |
|
158 |
|
159 // 1 |
|
160 val trans1 : NTrans = Set( |
|
161 { case (Q0, 'a') => Q1 }, |
|
162 { case (Q0, _) => Q0 }, |
|
163 { case (Q1, _) => Q2 }, |
|
164 { case (Q2, _) => Q3 }, |
|
165 { case (Q3, _) => Q4 }, |
|
166 { case (Q4, 'b') => Q5 }, |
|
167 { case (Q5, 'c') => Q6 } |
|
168 ) |
|
169 |
|
170 val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6)) |
|
171 |
|
172 naccepts(nfa1, "axaybzbc") // true |
|
173 naccepts(nfa1, "aaaaxaybzbc") // true |
|
174 naccepts(nfa1, "axaybzbd") // false |
|
175 |
|
176 // the nfa has five states, which might be all |
|
177 // active |
|
178 |
|
179 max_accepts(nfa1, "axaybzbc") // 3 |
|
180 max_accepts(nfa1, "aaaaxaybzbc") // 5 |
|
181 max_accepts(nfa1, "axaybzbd") // 3 |
|
182 max_accepts(nfa1, "aaaaaaaaaaaaaxaybzbd") // 5 |
|
183 |
|
184 |
|
185 // 2 |
|
186 val trans2 : NTrans = Set( |
|
187 { case (Q0, 'a') => Q0 }, |
|
188 { case (Q0, 'a') => Q1 }, |
|
189 { case (Q0, 'b') => Q2 }, |
|
190 { case (Q1, 'a') => Q1 }, |
|
191 { case (Q2, 'b') => Q2 } |
|
192 ) |
|
193 |
|
194 val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2)) |
|
195 |
|
196 naccepts(nfa2, "aa") // false |
|
197 naccepts(nfa2, "aaaaa") // false |
|
198 naccepts(nfa2, "aaaaab") // true |
|
199 naccepts(nfa2, "aaaaabbb") // true |
|
200 naccepts(nfa2, "aaaaabbbaaa") // false |
|
201 naccepts(nfa2, "ac") // false |
|
202 |
|
203 // 3 |
|
204 val trans3 : NTrans = Set( |
|
205 { case (Q0, _) => Q0 }, |
|
206 { case (Q0, 'a') => Q1 }, |
|
207 { case (Q0, 'b') => Q3 }, |
|
208 { case (Q1, 'b') => Q2 }, |
|
209 { case (Q2, 'c') => Q5 }, |
|
210 { case (Q3, 'c') => Q4 }, |
|
211 { case (Q4, 'd') => Q5 } |
|
212 ) |
|
213 |
|
214 val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5)) |
|
215 |
|
216 naccepts(nfa3, "aaaaabc") // true |
|
217 naccepts(nfa3, "aaaabcd") // true |
|
218 naccepts(nfa3, "aaaaab") // false |
|
219 naccepts(nfa3, "aaaabc") // true |
|
220 naccepts(nfa3, "aaaaabbbaaa") // false |
|
221 |
|
222 |