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