2 // sets of states) |
2 // sets of states) |
3 // |
3 // |
4 // needs :load dfa.scala for states |
4 // needs :load dfa.scala for states |
5 |
5 |
6 |
6 |
7 // type abbreviation for partial functions |
7 // a type abbreviation for partial functions |
8 type :=>[A, B] = PartialFunction[A, B] |
8 type :=>[A, B] = PartialFunction[A, B] |
9 |
9 |
10 // return an empty set, when parial function is not defined |
10 // return an empty set, when a parial function is not defined |
11 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
11 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
12 Try(f(x)) getOrElse Set[B]() |
12 Try(f(x)) getOrElse Set[B]() |
13 |
13 |
14 |
14 |
15 // NFAs |
15 // NFAs |
16 case class NFA[A, C](starts: Set[A], // starting states |
16 case class NFA[A, C](starts: Set[A], // the starting states |
17 delta: (A, C) :=> Set[A], // transition function |
17 delta: (A, C) :=> Set[A], // the transition function |
18 fins: A => Boolean) { // final states |
18 fins: A => Boolean) { // the final states |
19 |
19 |
20 // given a state and a character, what is the set of |
20 // given a state and a character, what is the set of |
21 // next states? if there is none => empty set |
21 // next states? if there is none => empty set |
22 def next(q: A, c: C) : Set[A] = |
22 def next(q: A, c: C) : Set[A] = |
23 applyOrElse(delta, (q, c)) |
23 applyOrElse(delta, (q, c)) |