|
1 // DFAs in Scala using partial functions |
|
2 import scala.util.Try |
|
3 |
|
4 // a type abbreviation for partial functions |
|
5 type :=>[A, B] = PartialFunction[A, B] |
|
6 |
|
7 // main DFA class |
|
8 case class DFA[A, C](start: A, // the starting state |
|
9 delta: (A, C) :=> A, // transitions (partial fun) |
|
10 fins: A => Boolean) { // the final states |
|
11 |
|
12 def deltas(q: A, s: List[C]) : A = s match { |
|
13 case Nil => q |
|
14 case c::cs => deltas(delta(q, c), cs) |
|
15 } |
|
16 |
|
17 def accepts(s: List[C]) : Boolean = |
|
18 Try(fins(deltas(start, s))).getOrElse(false) |
|
19 } |
|
20 |
|
21 // the example shown in the handout |
|
22 abstract class State |
|
23 case object Q0 extends State |
|
24 case object Q1 extends State |
|
25 case object Q2 extends State |
|
26 case object Q3 extends State |
|
27 case object Q4 extends State |
|
28 |
|
29 val delta : (State, Char) :=> State = |
|
30 { case (Q0, 'a') => Q1 |
|
31 case (Q0, 'b') => Q2 |
|
32 case (Q1, 'a') => Q4 |
|
33 case (Q1, 'b') => Q2 |
|
34 case (Q2, 'a') => Q3 |
|
35 case (Q2, 'b') => Q2 |
|
36 case (Q3, 'a') => Q4 |
|
37 case (Q3, 'b') => Q0 |
|
38 case (Q4, 'a') => Q4 |
|
39 case (Q4, 'b') => Q4 } |
|
40 |
|
41 val dfa = DFA(Q0, delta, Set[State](Q4)) |
|
42 dfa.accepts("aaabbb".toList) |
|
43 |
|
44 dfa.accepts("bbabaab".toList) // true |
|
45 dfa.accepts("baba".toList) // false |
|
46 dfa.accepts("abc".toList) // false |
|
47 |
|
48 // another DFA test with a Sink state |
|
49 abstract class S |
|
50 case object S0 extends S |
|
51 case object S1 extends S |
|
52 case object S2 extends S |
|
53 case object Sink extends S |
|
54 |
|
55 // a transition function with a sink state |
|
56 val sigma : (S, Char) :=> S = |
|
57 { case (S0, 'a') => S1 |
|
58 case (S1, 'a') => S2 |
|
59 case _ => Sink |
|
60 } |
|
61 |
|
62 val dfa1a = DFA(S0, sigma, Set[S](S2)) |
|
63 |
|
64 dfa1a.accepts("aa".toList) // true |
|
65 dfa1a.accepts("".toList) // false |
|
66 dfa1a.accepts("ab".toList) // false |
|
67 |