// Thompson Construction (Part 1)+ −
// (needs :load dfa.scala+ −
// :load nfa.scala+ −
// :load enfa.scala)+ −
+ − + − // states for Thompson construction+ −
case class TState(i: Int) extends State+ −
+ − object TState {+ −
var counter = 0+ −
+ −
def apply() : TState = {+ −
counter += 1;+ −
new TState(counter - 1)+ −
}+ −
}+ −
+ − + − // a type abbreviation+ −
type NFAt = NFA[TState, Char]+ −
+ − + − // a NFA that does not accept any string+ −
def NFA_ZERO(): NFAt = {+ −
val Q = TState()+ −
NFA(Set(Q), { case _ => Set() }, Set())+ −
}+ −
+ − // a NFA that accepts the empty string+ −
def NFA_ONE() : NFAt = {+ −
val Q = TState()+ −
NFA(Set(Q), { case _ => Set() }, Set(Q))+ −
}+ −
+ − // a NFA that accepts the string "c"+ −
def NFA_CHAR(c: Char) : NFAt = {+ −
val Q1 = TState()+ −
val Q2 = TState()+ −
NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))+ −
}+ −