485
|
1 |
// NFAs in Scala using partial functions (returning
|
|
2 |
// sets of states)
|
491
|
3 |
//
|
733
|
4 |
|
|
5 |
// load dfas
|
|
6 |
import $file.dfa, dfa._
|
487
|
7 |
|
|
8 |
|
623
|
9 |
// return an empty set, when a parial function is not defined
|
733
|
10 |
import scala.util.Try
|
485
|
11 |
def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] =
|
733
|
12 |
Try(f(x)).getOrElse(Set[B]())
|
485
|
13 |
|
|
14 |
|
|
15 |
// NFAs
|
623
|
16 |
case class NFA[A, C](starts: Set[A], // the starting states
|
|
17 |
delta: (A, C) :=> Set[A], // the transition function
|
|
18 |
fins: A => Boolean) { // the final states
|
144
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
|
485
|
20 |
// given a state and a character, what is the set of
|
|
21 |
// next states? if there is none => empty set
|
482
|
22 |
def next(q: A, c: C) : Set[A] =
|
485
|
23 |
applyOrElse(delta, (q, c))
|
144
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
|
482
|
25 |
def nexts(qs: Set[A], c: C) : Set[A] =
|
|
26 |
qs.flatMap(next(_, c))
|
144
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
|
485
|
28 |
// given some states and a string, what is the set
|
|
29 |
// of next states?
|
482
|
30 |
def deltas(qs: Set[A], s: List[C]) : Set[A] = s match {
|
|
31 |
case Nil => qs
|
|
32 |
case c::cs => deltas(nexts(qs, c), cs)
|
144
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
|
485
|
35 |
// is a string accepted by an NFA?
|
482
|
36 |
def accepts(s: List[C]) : Boolean =
|
|
37 |
deltas(starts, s).exists(fins)
|
487
|
38 |
|
|
39 |
// depth-first version of accepts
|
|
40 |
def search(q: A, s: List[C]) : Boolean = s match {
|
|
41 |
case Nil => fins(q)
|
|
42 |
case c::cs => next(q, c).exists(search(_, cs))
|
|
43 |
}
|
|
44 |
|
|
45 |
def accepts2(s: List[C]) : Boolean =
|
|
46 |
starts.exists(search(_, s))
|
144
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
}
|
487
|
48 |
|
|
49 |
|
|
50 |
|
|
51 |
// NFA examples
|
|
52 |
|
|
53 |
val nfa_trans1 : (State, Char) :=> Set[State] =
|
|
54 |
{ case (Q0, 'a') => Set(Q0, Q1)
|
|
55 |
case (Q0, 'b') => Set(Q2)
|
|
56 |
case (Q1, 'a') => Set(Q1)
|
|
57 |
case (Q2, 'b') => Set(Q2) }
|
|
58 |
|
|
59 |
val nfa1 = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2))
|
|
60 |
|
733
|
61 |
println(nfa1.accepts("aa".toList)) // false
|
|
62 |
println(nfa1.accepts("aaaaa".toList)) // false
|
|
63 |
println(nfa1.accepts("aaaaab".toList)) // true
|
|
64 |
println(nfa1.accepts("aaaaabbb".toList)) // true
|
|
65 |
println(nfa1.accepts("aaaaabbbaaa".toList)) // false
|
|
66 |
println(nfa1.accepts("ac".toList)) // false
|
487
|
67 |
|
733
|
68 |
println(nfa1.accepts2("aa".toList)) // false
|
|
69 |
println(nfa1.accepts2("aaaaa".toList)) // false
|
|
70 |
println(nfa1.accepts2("aaaaab".toList)) // true
|
|
71 |
println(nfa1.accepts2("aaaaabbb".toList)) // true
|
|
72 |
println(nfa1.accepts2("aaaaabbbaaa".toList)) // false
|
|
73 |
println(nfa1.accepts2("ac".toList)) // false
|
488
|
74 |
|
|
75 |
|
|
76 |
|
|
77 |
|
|
78 |
// subset constructions
|
|
79 |
|
490
|
80 |
def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {
|
|
81 |
DFA(nfa.starts,
|
|
82 |
{ case (qs, c) => nfa.nexts(qs, c) },
|
|
83 |
_.exists(nfa.fins))
|
|
84 |
}
|
|
85 |
|
733
|
86 |
println(subset(nfa1).accepts("aa".toList)) // false
|
|
87 |
println(subset(nfa1).accepts("aaaaa".toList)) // false
|
|
88 |
println(subset(nfa1).accepts("aaaaab".toList)) // true
|
|
89 |
println(subset(nfa1).accepts("aaaaabbb".toList)) // true
|
|
90 |
println(subset(nfa1).accepts("aaaaabbbaaa".toList)) // false
|
|
91 |
println(subset(nfa1).accepts("ac".toList)) // false
|
652
|
92 |
|