1 // DFAs |
1 // DFAs in Scala based on partial functions |
2 import scala.util._ |
2 import scala.util.Try |
3 |
3 |
4 abstract class State |
4 // type abbreviation for partial functions |
5 type States = Set[State] |
5 type :=>[A, B] = PartialFunction[A, B] |
6 |
6 |
7 case class IntState(i: Int) extends State |
7 case class DFA[A, C](start: A, // starting state |
|
8 delta: (A, C) :=> A, // transition partial fun |
|
9 fins: A => Boolean) { // final states |
8 |
10 |
9 object NewState { |
11 def deltas(q: A, s: List[C]) : A = s match { |
10 var counter = 0 |
12 case Nil => q |
11 |
13 case c::cs => deltas(delta(q, c), cs) |
12 def apply() : IntState = { |
|
13 counter += 1; |
|
14 new IntState(counter - 1) |
|
15 } |
14 } |
|
15 |
|
16 def accepts(s: List[C]) : Boolean = |
|
17 Try(fins(deltas(start, s))) getOrElse false |
16 } |
18 } |
17 |
19 |
|
20 // the example shown earlier in the handout |
|
21 abstract class State |
|
22 case object Q0 extends State |
|
23 case object Q1 extends State |
|
24 case object Q2 extends State |
|
25 case object Q3 extends State |
|
26 case object Q4 extends State |
18 |
27 |
19 // DFA class |
28 val delta : (State, Char) :=> State = |
20 case class DFA(states: States, |
29 { case (Q0, 'a') => Q1 |
21 start: State, |
30 case (Q0, 'b') => Q2 |
22 delta: (State, Char) => State, |
31 case (Q1, 'a') => Q4 |
23 fins: States) { |
32 case (Q1, 'b') => Q2 |
24 |
33 case (Q2, 'a') => Q3 |
25 def deltas(q: State, s: List[Char]) : State = s match { |
34 case (Q2, 'b') => Q2 |
26 case Nil => q |
35 case (Q3, 'a') => Q4 |
27 case c::cs => deltas(delta(q, c), cs) |
36 case (Q3, 'b') => Q0 |
28 } |
37 case (Q4, 'a') => Q4 |
29 |
38 case (Q4, 'b') => Q4 } |
30 // wether a string is accepted by the automaton or not |
|
31 def accepts(s: String) : Boolean = |
|
32 Try(fins contains |
|
33 (deltas(start, s.toList))) getOrElse false |
|
34 } |
|
35 |
39 |
|
40 val dfa = DFA(Q0, delta, Set[State](Q4)) |
36 |
41 |
37 // example DFA from the lectures |
42 dfa.accepts("bbabaab".toList) // true |
38 val Q0 = NewState() |
43 dfa.accepts("baba".toList) // false |
39 val Q1 = NewState() |
|
40 val Q2 = NewState() |
|
41 val Q3 = NewState() |
|
42 val Q4 = NewState() |
|
43 |
|
44 |
|
45 val delta : (State, Char) => State = { |
|
46 case (Q0, 'a') => Q1 |
|
47 case (Q0, 'b') => Q2 |
|
48 case (Q1, 'a') => Q4 |
|
49 case (Q1, 'b') => Q2 |
|
50 case (Q2, 'a') => Q3 |
|
51 case (Q2, 'b') => Q2 |
|
52 case (Q3, 'a') => Q4 |
|
53 case (Q3, 'b') => Q0 |
|
54 case (Q4, 'a') => Q4 |
|
55 case (Q4, 'b') => Q4 |
|
56 } |
|
57 |
|
58 val DFA1 = DFA(Set(Q0, Q1, Q2, Q3, Q4), Q0, delta, Set(Q4)) |
|
59 |
|
60 println(DFA1.accepts("aaa")) |
|
61 println(DFA1.accepts("bb")) |
|
62 println(DFA1.accepts("aaac")) |
|
63 |
|
64 |
|