1 // NFAs in Scala based on sets of partial functions |
1 // NFAs in Scala using partial functions (returning |
|
2 // sets of states) |
|
3 import scala.util.Try |
2 |
4 |
3 // type abbreviation for partial functions |
5 // type abbreviation for partial functions |
4 type :=>[A, B] = PartialFunction[A, B] |
6 type :=>[A, B] = PartialFunction[A, B] |
5 |
7 |
|
8 // return an empty set when not defined |
|
9 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
|
10 Try(f(x)) getOrElse Set[B]() |
|
11 |
|
12 |
|
13 // NFAs |
6 case class NFA[A, C](starts: Set[A], // starting states |
14 case class NFA[A, C](starts: Set[A], // starting states |
7 delta: Set[(A, C) :=> A], // transitions |
15 delta: (A, C) :=> Set[A], // transition function |
8 fins: A => Boolean) { // final states |
16 fins: A => Boolean) { // final states |
9 |
17 |
10 // given a state and a character, what is the set of next states? |
18 // given a state and a character, what is the set of |
11 // if there is none => empty set |
19 // next states? if there is none => empty set |
12 def next(q: A, c: C) : Set[A] = |
20 def next(q: A, c: C) : Set[A] = |
13 delta.flatMap(d => Try(d(q, c)).toOption) |
21 applyOrElse(delta, (q, c)) |
14 |
22 |
15 def nexts(qs: Set[A], c: C) : Set[A] = |
23 def nexts(qs: Set[A], c: C) : Set[A] = |
16 qs.flatMap(next(_, c)) |
24 qs.flatMap(next(_, c)) |
17 |
25 |
|
26 // given some states and a string, what is the set |
|
27 // of next states? |
18 def deltas(qs: Set[A], s: List[C]) : Set[A] = s match { |
28 def deltas(qs: Set[A], s: List[C]) : Set[A] = s match { |
19 case Nil => qs |
29 case Nil => qs |
20 case c::cs => deltas(nexts(qs, c), cs) |
30 case c::cs => deltas(nexts(qs, c), cs) |
21 } |
31 } |
22 |
32 |
|
33 // is a string accepted by an NFA? |
23 def accepts(s: List[C]) : Boolean = |
34 def accepts(s: List[C]) : Boolean = |
24 deltas(starts, s).exists(fins) |
35 deltas(starts, s).exists(fins) |
25 } |
36 } |
26 |
|