| author | Christian Urban <urbanc@in.tum.de> |
| Fri, 28 Apr 2017 11:01:25 +0100 | |
| changeset 487 | ffbc65112d48 |
| parent 485 | 21dec9df46ba |
| child 488 | 057b4603b940 |
| 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 |
|
| 487 | 5 |
// states class |
6 |
abstract class State |
|
7 |
case object Q0 extends State |
|
8 |
case object Q1 extends State |
|
9 |
case object Q2 extends State |
|
10 |
case object Q3 extends State |
|
11 |
case object Q4 extends State |
|
12 |
||
13 |
||
14 |
||
| 482 | 15 |
// type abbreviation for partial functions |
16 |
type :=>[A, B] = PartialFunction[A, B] |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
|
| 485 | 18 |
// return an empty set when not defined |
19 |
def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
|
20 |
Try(f(x)) getOrElse Set[B]() |
|
21 |
||
22 |
||
23 |
// NFAs |
|
| 487 | 24 |
case class NFA[A, C](starts: Set[A], // starting states |
25 |
delta: (A, C) :=> Set[A], // transition function |
|
26 |
fins: A => Boolean) { // final states
|
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
|
| 485 | 28 |
// given a state and a character, what is the set of |
29 |
// next states? if there is none => empty set |
|
| 482 | 30 |
def next(q: A, c: C) : Set[A] = |
| 485 | 31 |
applyOrElse(delta, (q, c)) |
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
|
| 482 | 33 |
def nexts(qs: Set[A], c: C) : Set[A] = |
34 |
qs.flatMap(next(_, c)) |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
|
| 485 | 36 |
// given some states and a string, what is the set |
37 |
// of next states? |
|
| 482 | 38 |
def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {
|
39 |
case Nil => qs |
|
40 |
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
|
41 |
} |
|
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
|
| 485 | 43 |
// is a string accepted by an NFA? |
| 482 | 44 |
def accepts(s: List[C]) : Boolean = |
45 |
deltas(starts, s).exists(fins) |
|
| 487 | 46 |
|
47 |
// depth-first version of accepts |
|
48 |
def search(q: A, s: List[C]) : Boolean = s match {
|
|
49 |
case Nil => fins(q) |
|
50 |
case c::cs => next(q, c).exists(search(_, cs)) |
|
51 |
} |
|
52 |
||
53 |
def accepts2(s: List[C]) : Boolean = |
|
54 |
starts.exists(search(_, s)) |
|
|
144
0cb61bed557d
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
} |
| 487 | 56 |
|
57 |
||
58 |
||
59 |
// NFA examples |
|
60 |
||
61 |
val nfa_trans1 : (State, Char) :=> Set[State] = |
|
62 |
{ case (Q0, 'a') => Set(Q0, Q1)
|
|
63 |
case (Q0, 'b') => Set(Q2) |
|
64 |
case (Q1, 'a') => Set(Q1) |
|
65 |
case (Q2, 'b') => Set(Q2) } |
|
66 |
||
67 |
val nfa1 = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2)) |
|
68 |
||
69 |
nfa1.accepts("aa".toList) // false
|
|
70 |
nfa1.accepts("aaaaa".toList) // false
|
|
71 |
nfa1.accepts("aaaaab".toList) // true
|
|
72 |
nfa1.accepts("aaaaabbb".toList) // true
|
|
73 |
nfa1.accepts("aaaaabbbaaa".toList) // false
|
|
74 |
nfa1.accepts("ac".toList) // false
|
|
75 |
||
76 |
nfa1.accepts2("aa".toList) // false
|
|
77 |
nfa1.accepts2("aaaaa".toList) // false
|
|
78 |
nfa1.accepts2("aaaaab".toList) // true
|
|
79 |
nfa1.accepts2("aaaaabbb".toList) // true
|
|
80 |
nfa1.accepts2("aaaaabbbaaa".toList) // false
|
|
81 |
nfa1.accepts2("ac".toList) // false
|