blob: 12049e0012887e4a47b3475784bd0f35c56c1886 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
package scala.util.automata ;
import scala.collection.{ Set, Map };
/** A deterministic automaton. States are integers, where
* 0 is always the only initial state. Transitions are represented
* in the delta function. A default transitions is one that
* is taken when no other transition can be taken.
* All states are reachable. Accepting states are those for which
* the partial function 'finals' is defined.
*/
abstract class DetWordAutom[T <: AnyRef] {
val nstates: Int;
val finals: Array[Int] ;
val delta: Array[Map[T,Int]];
val default: Array[Int] ;
def isFinal(q: Int) = finals(q) != 0;
def isSink(q: Int) = delta(q).isEmpty && default(q) == q;
def next(q: Int, label: T) = {
delta(q).get(label) match {
case Some(p) => p
case _ => default(q)
}
}
override def toString() = {
val sb = new StringBuffer();
sb.append("[DetWordAutom nstates=");
sb.append(nstates);
sb.append(" finals=");
var map = new scala.collection.immutable.ListMap[Int,Int];
var j = 0; while( j < nstates ) {
if(j < finals.length)
map = map.update(j,finals(j));
j = j + 1;
}
sb.append(map.toString());
sb.append(" delta=\n");
for( val i <- Iterator.range(0,nstates)) {
sb.append( i );
sb.append("->");
sb.append(delta(i).toString());
sb.append('\n');
if(i < default.length) {
sb.append("_>");
sb.append(default(i).toString());
sb.append('\n');
}
}
sb.toString();
}
}
|