|
1 |
|
2 // a class for deterministic finite automata, |
|
3 // the type of states is kept polymorphic |
|
4 |
|
5 case class Automaton[A](start: A, states: Set[A], delta: Map[(A, Char), A], fins: Set[A]) { |
|
6 |
|
7 // the transition function lifted to list of characters |
|
8 def deltas(q: A, cs: List[Char]) : A = |
|
9 if (states.contains(q)) cs match { |
|
10 case Nil => q |
|
11 case c::cs => |
|
12 if (delta.isDefinedAt(q, c)) deltas(delta(q, c), cs) |
|
13 else throw new RuntimeException(q + " does not have a transition for " + c) |
|
14 } |
|
15 else throw new RuntimeException(q + " is not a state of the automaton") |
|
16 |
|
17 // wether a string is accepted by the automaton |
|
18 def accepts(s: String) = |
|
19 try { |
|
20 fins.contains(deltas(start, s.toList)) |
|
21 } catch { |
|
22 case e:RuntimeException => false |
|
23 } |
|
24 } |
|
25 |
|
26 |
|
27 |
|
28 abstract class Rexp |
|
29 |
|
30 case object NULL extends Rexp |
|
31 case object EMPTY extends Rexp |
|
32 case class CHAR(c: Char) extends Rexp |
|
33 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
34 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
35 case class STAR(r: Rexp) extends Rexp |
|
36 |
|
37 implicit def string2rexp(s : String) = { |
|
38 def chars2rexp (cs: List[Char]) : Rexp = cs match { |
|
39 case Nil => EMPTY |
|
40 case c::Nil => CHAR(c) |
|
41 case c::cs => SEQ(CHAR(c), chars2rexp(cs)) |
|
42 } |
|
43 chars2rexp(s.toList) |
|
44 } |
|
45 |
|
46 def nullable (r: Rexp) : Boolean = r match { |
|
47 case NULL => false |
|
48 case EMPTY => true |
|
49 case CHAR(_) => false |
|
50 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
51 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
52 case STAR(_) => true |
|
53 } |
|
54 |
|
55 def der (r: Rexp, c: Char) : Rexp = r match { |
|
56 case NULL => NULL |
|
57 case EMPTY => NULL |
|
58 case CHAR(d) => if (c == d) EMPTY else NULL |
|
59 case ALT(r1, r2) => ALT(der(r1, c), der(r2, c)) |
|
60 case SEQ(r1, r2) => if (nullable(r1)) ALT(SEQ(der(r1, c), r2), der(r2, c)) |
|
61 else SEQ(der(r1, c), r2) |
|
62 case STAR(r) => SEQ(der(r, c), STAR(r)) |
|
63 } |
|
64 |
|
65 |
|
66 // Here we construct an automaton whose |
|
67 // states are regular expressions |
|
68 type State = Rexp |
|
69 type States = Set[State] |
|
70 type Transition = Map[(State, Char), State] |
|
71 |
|
72 def goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = { |
|
73 val qc : State = der(q, c) |
|
74 if (qs.contains(qc)) (qs, delta + ((q, c) -> q)) |
|
75 else explore(qs + qc, delta + ((q, c) -> qc), qc) |
|
76 } |
|
77 |
|
78 // we use as alphabet all lowercase letters |
|
79 val alphabet = "abcdefghijklmnopqrstuvwxyz".toSet |
|
80 |
|
81 def explore (qs: States, delta: Transition, q: State) : (States, Transition) = |
|
82 alphabet.foldRight[(States, Transition)] (qs, delta) ((c, qsd) => goto(q, c, qsd._1, qsd._2)) |
|
83 |
|
84 |
|
85 def mk_automaton (r: Rexp) : Automaton[Rexp] = { |
|
86 val (qs, delta) = explore(Set(r), Map(), r); |
|
87 val fins = for (q <- qs if nullable(q)) yield q; |
|
88 Automaton[Rexp](r, qs, delta, fins) |
|
89 } |
|
90 |
|
91 val A = mk_automaton(ALT("ab","ac")) |
|
92 |
|
93 println(A.accepts("bd")) |
|
94 println(A.accepts("ab")) |
|
95 println(A.accepts("ac")) |