equal
deleted
inserted
replaced
1 // DFAs in Scala using partial functions |
1 // DFAs in Scala using partial functions |
2 import scala.util.Try |
2 import scala.util.Try |
3 |
3 |
4 // type abbreviation for partial functions |
4 // a type abbreviation for partial functions |
5 type :=>[A, B] = PartialFunction[A, B] |
5 type :=>[A, B] = PartialFunction[A, B] |
6 |
6 |
7 |
7 |
8 case class DFA[A, C](start: A, // starting state |
8 case class DFA[A, C](start: A, // the starting state |
9 delta: (A, C) :=> A, // transition (partial fun) |
9 delta: (A, C) :=> A, // transitions (partial fun) |
10 fins: A => Boolean) { // final states |
10 fins: A => Boolean) { // the final states |
11 |
11 |
12 def deltas(q: A, s: List[C]) : A = s match { |
12 def deltas(q: A, s: List[C]) : A = s match { |
13 case Nil => q |
13 case Nil => q |
14 case c::cs => deltas(delta(q, c), cs) |
14 case c::cs => deltas(delta(q, c), cs) |
15 } |
15 } |
50 case object S0 extends S |
50 case object S0 extends S |
51 case object S1 extends S |
51 case object S1 extends S |
52 case object S2 extends S |
52 case object S2 extends S |
53 case object Sink extends S |
53 case object Sink extends S |
54 |
54 |
55 // transition function with a sink state |
55 // a transition function with a sink state |
56 val sigma : (S, Char) :=> S = |
56 val sigma : (S, Char) :=> S = |
57 { case (S0, 'a') => S1 |
57 { case (S0, 'a') => S1 |
58 case (S1, 'a') => S2 |
58 case (S1, 'a') => S2 |
59 case _ => Sink |
59 case _ => Sink |
60 } |
60 } |