|
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 |
|
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 |
|
52 |
|
53 // (3) Write a function that takes a transition, a state |
|
54 // and a list of characters as arguments and produces |
|
55 // the state generated by following the transitions for |
|
56 // each character in the list. |
|
57 |
|
58 def nexts(trans: Trans, q: State, s: List[Char]) : Option[State] = ... |
|
59 |
|
60 |
|
61 |
|
62 // class for DFAs |
|
63 case class DFA(start: State, // starting state |
|
64 trans: Trans, // transition |
|
65 fins: States) // final states |
|
66 |
|
67 // (4) Write a function that tests whether a string is accepted |
|
68 // by an DFA or not. |
|
69 |
|
70 def accepts(dfa: DFA, s: String) : Boolean = ... |
|
71 |
|
72 |
|
73 |
|
74 // DFA examples |
|
75 |
|
76 val dtrans1 : Trans = |
|
77 { case (Q0, 'a') => Q0 |
|
78 case (Q0, 'b') => Q1 |
|
79 } |
|
80 |
|
81 val dfa1 = DFA(Q0, dtrans1, Set[State](Q1)) |
|
82 |
|
83 accepts(dfa1, "aaab") // true |
|
84 accepts(dfa1, "aacb") // false |
|
85 |
|
86 |
|
87 // NFAs |
|
88 |
|
89 |
|
90 // (5) Write a function that takes a transition set, a state |
|
91 // and a character as arguments, and calculates all possible |
|
92 // next states (returned as set). |
|
93 |
|
94 def nnext(trans: NTrans, q: State, c: Char) : States = ... |
|
95 |
|
96 |
|
97 // (6) Write a function that takes a transition set, a set of states |
|
98 // and a character as arguments, and calculates all possible |
|
99 // next states that can be reached from any state in the set. |
|
100 |
|
101 def nnexts(trans: NTrans, qs: States, c: Char) : States = ... |
|
102 |
|
103 |
|
104 |
|
105 // (7) Write a function that lifts nnexts from from single |
|
106 // characters to lists of characters. |
|
107 def nnextss(trans: NTrans, qs: States, s: List[Char]) : States = ... |
|
108 |
|
109 |
|
110 // class for NFAs |
|
111 case class NFA(start: States, // starting state |
|
112 trans: NTrans, // transition edges |
|
113 fins: States) // final states |
|
114 |
|
115 |
|
116 // (8) Write a function that tests whether a string is |
|
117 // accepted by an NFA or not. |
|
118 |
|
119 def naccepts(nfa: NFA, s: String) : Boolean = ... |
|
120 |
|
121 |
|
122 // (9) Write similar functions as in (7) and (8), but instead of |
|
123 // returning states or a boolean, calculate the number of states |
|
124 // that need to be followed in each step. |
|
125 |
|
126 def max_nextss(trans: NTrans, qs: States, s: List[Char], max: Int) : Int = ... |
|
127 |
|
128 def max_accepts(nfa: NFA, s: String) : Int = ... |
|
129 |
|
130 |
|
131 // NFA examples |
|
132 |
|
133 |
|
134 // 1 |
|
135 val trans1 : NTrans = Set( |
|
136 { case (Q0, 'a') => Q1 }, |
|
137 { case (Q0, _) => Q0 }, |
|
138 { case (Q1, _) => Q2 }, |
|
139 { case (Q2, _) => Q3 }, |
|
140 { case (Q3, _) => Q4 }, |
|
141 { case (Q4, 'b') => Q5 }, |
|
142 { case (Q5, 'c') => Q6 } |
|
143 ) |
|
144 |
|
145 val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6)) |
|
146 |
|
147 naccepts(nfa1, "axaybzbc") // true |
|
148 naccepts(nfa1, "aaaaxaybzbc") // true |
|
149 naccepts(nfa1, "axaybzbd") // false |
|
150 |
|
151 // the nfa has five states, which might be all |
|
152 // active |
|
153 |
|
154 max_accepts(nfa1, "axaybzbc") // 3 |
|
155 max_accepts(nfa1, "aaaaxaybzbc") // 5 |
|
156 max_accepts(nfa1, "axaybzbd") // 3 |
|
157 max_accepts(nfa1, "aaaaaaaaaaaaaxaybzbd") // 5 |
|
158 |
|
159 |
|
160 // 2 |
|
161 val trans2 : NTrans = Set( |
|
162 { case (Q0, 'a') => Q0 }, |
|
163 { case (Q0, 'a') => Q1 }, |
|
164 { case (Q0, 'b') => Q2 }, |
|
165 { case (Q1, 'a') => Q1 }, |
|
166 { case (Q2, 'b') => Q2 } |
|
167 ) |
|
168 |
|
169 val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2)) |
|
170 |
|
171 naccepts(nfa2, "aa") // false |
|
172 naccepts(nfa2, "aaaaa") // false |
|
173 naccepts(nfa2, "aaaaab") // true |
|
174 naccepts(nfa2, "aaaaabbb") // true |
|
175 naccepts(nfa2, "aaaaabbbaaa") // false |
|
176 naccepts(nfa2, "ac") // false |
|
177 |
|
178 // 3 |
|
179 val trans3 : NTrans = Set( |
|
180 { case (Q0, _) => Q0 }, |
|
181 { case (Q0, 'a') => Q1 }, |
|
182 { case (Q0, 'b') => Q3 }, |
|
183 { case (Q1, 'b') => Q2 }, |
|
184 { case (Q2, 'c') => Q5 }, |
|
185 { case (Q3, 'c') => Q4 }, |
|
186 { case (Q4, 'd') => Q5 } |
|
187 ) |
|
188 |
|
189 val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5)) |
|
190 |
|
191 naccepts(nfa3, "aaaaabc") // true |
|
192 naccepts(nfa3, "aaaabcd") // true |
|
193 naccepts(nfa3, "aaaaab") // false |
|
194 naccepts(nfa3, "aaaabc") // true |
|
195 naccepts(nfa3, "aaaaabbbaaa") // false |
|
196 |
|
197 |