|
487
|
1 |
// Thompson Construction (Part 1)
|
|
|
2 |
// (needs :load nfa.scala
|
|
|
3 |
// :load enfa.scala)
|
|
|
4 |
|
|
|
5 |
|
|
|
6 |
// states for Thompson construction
|
|
|
7 |
case class TState(i: Int) extends State
|
|
|
8 |
|
|
|
9 |
object TState {
|
|
|
10 |
var counter = 0
|
|
|
11 |
|
|
|
12 |
def apply() : TState = {
|
|
|
13 |
counter += 1;
|
|
|
14 |
new TState(counter - 1)
|
|
|
15 |
}
|
|
|
16 |
}
|
|
|
17 |
|
|
|
18 |
|
|
488
|
19 |
// a type abbreviation
|
|
487
|
20 |
type NFAt = NFA[TState, Char]
|
|
|
21 |
|
|
|
22 |
|
|
488
|
23 |
// a NFA that does not accept any string
|
|
487
|
24 |
def NFA_ZERO(): NFAt = {
|
|
|
25 |
val Q = TState()
|
|
|
26 |
NFA(Set(Q), { case _ => Set() }, Set())
|
|
|
27 |
}
|
|
|
28 |
|
|
488
|
29 |
// a NFA that accepts the empty string
|
|
487
|
30 |
def NFA_ONE() : NFAt = {
|
|
|
31 |
val Q = TState()
|
|
|
32 |
NFA(Set(Q), { case _ => Set() }, Set(Q))
|
|
|
33 |
}
|
|
|
34 |
|
|
488
|
35 |
// a NFA that accepts the string "c"
|
|
487
|
36 |
def NFA_CHAR(c: Char) : NFAt = {
|
|
|
37 |
val Q1 = TState()
|
|
|
38 |
val Q2 = TState()
|
|
|
39 |
NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))
|
|
|
40 |
}
|