67 // states are regular expressions |
67 // states are regular expressions |
68 type State = Rexp |
68 type State = Rexp |
69 type States = Set[State] |
69 type States = Set[State] |
70 type Transition = Map[(State, Char), State] |
70 type Transition = Map[(State, Char), State] |
71 |
71 |
|
72 // we use as an alphabet all lowercase letters |
|
73 val alphabet = "abcdefghijklmnopqrstuvwxyz".toSet |
|
74 |
72 def goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = { |
75 def goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = { |
73 val qc : State = der(q, c) |
76 val q_der : State = der(q, c) |
74 if (qs.contains(qc)) (qs, delta + ((q, c) -> q)) |
77 if (qs.contains(q_der)) (qs, delta + ((q, c) -> q)) |
75 else explore(qs + qc, delta + ((q, c) -> qc), qc) |
78 else explore(qs + q_der, delta + ((q, c) -> q_der), q_der) |
76 } |
79 } |
77 |
80 |
78 // we use as an alphabet all lowercase letters |
|
79 val alphabet = "abcdefghijklmnopqrstuvwxyz".toSet |
|
80 |
|
81 def explore (qs: States, delta: Transition, q: State) : (States, Transition) = |
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)) |
82 alphabet.foldRight[(States, Transition)] (qs, delta) ((c, qsd) => goto(q, c, qsd._1, qsd._2)) |
83 |
83 |
84 |
84 |
85 def mk_automaton (r: Rexp) : Automaton[Rexp] = { |
85 def mk_automaton (r: Rexp) : Automaton[Rexp] = { |