| author | Christian Urban <urbanc@in.tum.de> |
| Tue, 25 Apr 2017 12:28:07 +0100 | |
| changeset 485 | bd6d999ab7b6 |
| parent 483 | 6f508bcdaa30 |
| child 487 | a697421eaa04 |
| permissions | -rw-r--r-- |
| 485 | 1 |
// NFAs in Scala using partial functions (returning |
2 |
// sets of states) |
|
3 |
import scala.util.Try |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
|
| 482 | 5 |
// type abbreviation for partial functions |
6 |
type :=>[A, B] = PartialFunction[A, B] |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
| 485 | 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 |
|
| 482 | 14 |
case class NFA[A, C](starts: Set[A], // starting states |
| 485 | 15 |
delta: (A, C) :=> Set[A], // transition function |
| 482 | 16 |
fins: A => Boolean) { // final states
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
|
| 485 | 18 |
// given a state and a character, what is the set of |
19 |
// next states? if there is none => empty set |
|
| 482 | 20 |
def next(q: A, c: C) : Set[A] = |
| 485 | 21 |
applyOrElse(delta, (q, c)) |
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
|
| 482 | 23 |
def nexts(qs: Set[A], c: C) : Set[A] = |
24 |
qs.flatMap(next(_, c)) |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
|
| 485 | 26 |
// given some states and a string, what is the set |
27 |
// of next states? |
|
| 482 | 28 |
def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {
|
29 |
case Nil => qs |
|
30 |
case c::cs => deltas(nexts(qs, c), cs) |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
} |
|
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
|
| 485 | 33 |
// is a string accepted by an NFA? |
| 482 | 34 |
def accepts(s: List[C]) : Boolean = |
35 |
deltas(starts, s).exists(fins) |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
} |