1 // NFAs in Scala using partial functions (returning |
|
2 // sets of states) |
|
3 // |
|
4 // needs :load dfa.scala for states |
|
5 |
|
6 |
|
7 // a type abbreviation for partial functions |
|
8 type :=>[A, B] = PartialFunction[A, B] |
|
9 |
|
10 // return an empty set, when a parial function is not defined |
|
11 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
|
12 Try(f(x)) getOrElse Set[B]() |
|
13 |
|
14 |
|
15 // NFAs |
|
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 |
|
19 |
|
20 // given a state and a character, what is the set of |
|
21 // next states? if there is none => empty set |
|
22 def next(q: A, c: C) : Set[A] = |
|
23 applyOrElse(delta, (q, c)) |
|
24 |
|
25 def nexts(qs: Set[A], c: C) : Set[A] = |
|
26 qs.flatMap(next(_, c)) |
|
27 |
|
28 // given some states and a string, what is the set |
|
29 // of next states? |
|
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) |
|
33 } |
|
34 |
|
35 // is a string accepted by an NFA? |
|
36 def accepts(s: List[C]) : Boolean = |
|
37 deltas(starts, s).exists(fins) |
|
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)) |
|
47 } |
|
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 |
|
61 nfa1.accepts("aa".toList) // false |
|
62 nfa1.accepts("aaaaa".toList) // false |
|
63 nfa1.accepts("aaaaab".toList) // true |
|
64 nfa1.accepts("aaaaabbb".toList) // true |
|
65 nfa1.accepts("aaaaabbbaaa".toList) // false |
|
66 nfa1.accepts("ac".toList) // false |
|
67 |
|
68 nfa1.accepts2("aa".toList) // false |
|
69 nfa1.accepts2("aaaaa".toList) // false |
|
70 nfa1.accepts2("aaaaab".toList) // true |
|
71 nfa1.accepts2("aaaaabbb".toList) // true |
|
72 nfa1.accepts2("aaaaabbbaaa".toList) // false |
|
73 nfa1.accepts2("ac".toList) // false |
|
74 |
|
75 |
|
76 |
|
77 |
|
78 // subset constructions |
|
79 |
|
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 |
|
86 subset(nfa1).accepts("aa".toList) // false |
|
87 subset(nfa1).accepts("aaaaa".toList) // false |
|
88 subset(nfa1).accepts("aaaaab".toList) // true |
|
89 subset(nfa1).accepts("aaaaabbb".toList) // true |
|
90 subset(nfa1).accepts("aaaaabbbaaa".toList) // false |
|
91 subset(nfa1).accepts("ac".toList) // false |
|
92 |
|