|
1 // NFAs based on Scala's partial functions |
|
2 |
|
3 |
|
4 // function that tests whether the intersection of two sets |
|
5 // is non-empty |
|
6 def share[A](a: Set[A], b: Set[A]) : Boolean = |
|
7 !(a intersect b).isEmpty |
|
8 |
|
9 share(Set(1,2,3), Set(2, 3, 4)) // true |
|
10 share(Set(1,2,3), Set(4, 5, 6)) // false |
|
11 |
|
12 // nodes of the NFAs |
|
13 abstract class State |
|
14 type States = Set[State] |
|
15 |
|
16 // edges of the NFAs |
|
17 type Edge = PartialFunction[(State, Char), State] |
|
18 type Edges = Set[Edge] |
|
19 |
|
20 |
|
21 // gives a new state, when the edge fires |
|
22 def fire(e: Edge, qc: (State, Char)) : Option[State] = |
|
23 if (e.isDefinedAt(qc)) Some(e(qc)) else None |
|
24 |
|
25 |
|
26 // class for NFAs |
|
27 case class NFA(start: State, // starting state |
|
28 trans: Edges, // transition edges |
|
29 fins: States) // final states |
|
30 |
|
31 |
|
32 // given the transitions and a state/character, |
|
33 // what are the set of next states? |
|
34 def next(trans: Edges, q: State, c: Char) : States = { |
|
35 trans.map(fire(_, (q, c))).flatten |
|
36 } |
|
37 |
|
38 // given the transitions and some states/character, |
|
39 // what are the set of next states? |
|
40 def nexts(trans: Edges, qs: States, c: Char) : States = { |
|
41 qs.flatMap(next(trans, _, c)) |
|
42 } |
|
43 |
|
44 |
|
45 // given the transitions, some states and a string, |
|
46 // what are the set of next states? |
|
47 def nextss(trans: Edges, qs: States, s: List[Char]) : States = s match { |
|
48 case Nil => qs |
|
49 case c::cs => nextss(trans, nexts(trans, qs, c), cs) |
|
50 } |
|
51 |
|
52 // is a string accepted by an NFA? |
|
53 def accepts(nfa: NFA, s: String) : Boolean = { |
|
54 share(nextss(nfa.trans, Set(nfa.start), s.toList), nfa.fins) |
|
55 } |
|
56 |
|
57 |
|
58 // test cases |
|
59 case object Q0 extends State |
|
60 case object Q1 extends State |
|
61 case object Q2 extends State |
|
62 case object Q3 extends State |
|
63 case object Q4 extends State |
|
64 case object Q5 extends State |
|
65 case object Q6 extends State |
|
66 |
|
67 // 1 |
|
68 val trans1 = Set[Edge]( |
|
69 { case (Q0, 'a') => Q1 }, |
|
70 { case (Q0, _) => Q0 }, |
|
71 { case (Q1, _) => Q2 }, |
|
72 { case (Q2, _) => Q3 }, |
|
73 { case (Q3, _) => Q4 }, |
|
74 { case (Q4, 'b') => Q5 }, |
|
75 { case (Q5, 'c') => Q6 } |
|
76 ) |
|
77 |
|
78 val nfa1 = NFA(Q0, trans1, Set[State](Q6)) |
|
79 |
|
80 accepts(nfa1, "axaybzbc") // true |
|
81 accepts(nfa1, "aaaaxaybzbc") // true |
|
82 accepts(nfa1, "axaybzbd") // false |
|
83 |
|
84 |
|
85 // 2 |
|
86 val trans2 = Set[Edge]( |
|
87 { case (Q0, 'a') => Q0 }, |
|
88 { case (Q0, 'a') => Q1 }, |
|
89 { case (Q0, 'b') => Q2 }, |
|
90 { case (Q1, 'a') => Q1 }, |
|
91 { case (Q2, 'b') => Q2 } |
|
92 ) |
|
93 |
|
94 val nfa2 = NFA(Q0, trans2, Set[State](Q2)) |
|
95 |
|
96 accepts(nfa2, "aa") // false |
|
97 accepts(nfa2, "aaaaa") // false |
|
98 accepts(nfa2, "aaaaab") // true |
|
99 accepts(nfa2, "aaaaabbb") // true |
|
100 accepts(nfa2, "aaaaabbbaaa") // false |
|
101 accepts(nfa2, "ac") // false |
|
102 |
|
103 // 3 |
|
104 val trans3 = Set[Edge]( |
|
105 { case (Q0, _) => Q0 }, |
|
106 { case (Q0, 'a') => Q1 }, |
|
107 { case (Q0, 'b') => Q3 }, |
|
108 { case (Q1, 'b') => Q2 }, |
|
109 { case (Q2, 'c') => Q5 }, |
|
110 { case (Q3, 'c') => Q4 }, |
|
111 { case (Q4, 'd') => Q5 } |
|
112 ) |
|
113 |
|
114 val nfa3 = NFA(Q0, trans3, Set[State](Q5)) |
|
115 |
|
116 accepts(nfa3, "aaaaabc") // true |
|
117 accepts(nfa3, "aaaabcd") // true |
|
118 accepts(nfa3, "aaaaab") // false |
|
119 accepts(nfa3, "aaaabc") // true |
|
120 accepts(nfa3, "aaaaabbbaaa") // false |
|
121 |
|
122 |