1 // NFAs in Scala using partial functions (returning |
1 // NFAs in Scala using partial functions (returning |
2 // sets of states) |
2 // sets of states) |
3 import scala.util.Try |
3 import scala.util.Try |
|
4 |
|
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 |
4 |
14 |
5 // type abbreviation for partial functions |
15 // type abbreviation for partial functions |
6 type :=>[A, B] = PartialFunction[A, B] |
16 type :=>[A, B] = PartialFunction[A, B] |
7 |
17 |
8 // return an empty set when not defined |
18 // return an empty set when not defined |
9 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
19 def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = |
10 Try(f(x)) getOrElse Set[B]() |
20 Try(f(x)) getOrElse Set[B]() |
11 |
21 |
12 |
22 |
13 // NFAs |
23 // NFAs |
14 case class NFA[A, C](starts: Set[A], // starting states |
24 case class NFA[A, C](starts: Set[A], // starting states |
15 delta: (A, C) :=> Set[A], // transition function |
25 delta: (A, C) :=> Set[A], // transition function |
16 fins: A => Boolean) { // final states |
26 fins: A => Boolean) { // final states |
17 |
27 |
18 // given a state and a character, what is the set of |
28 // given a state and a character, what is the set of |
19 // next states? if there is none => empty set |
29 // next states? if there is none => empty set |
20 def next(q: A, c: C) : Set[A] = |
30 def next(q: A, c: C) : Set[A] = |
21 applyOrElse(delta, (q, c)) |
31 applyOrElse(delta, (q, c)) |
31 } |
41 } |
32 |
42 |
33 // is a string accepted by an NFA? |
43 // is a string accepted by an NFA? |
34 def accepts(s: List[C]) : Boolean = |
44 def accepts(s: List[C]) : Boolean = |
35 deltas(starts, s).exists(fins) |
45 deltas(starts, s).exists(fins) |
|
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)) |
36 } |
55 } |
|
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 |