// Thompson Construction (Part 2)
// some more type abbreviations
type NFAtrans = (TState, Char) :=> Set[TState]
type eNFAtrans = (TState, Option[Char]) :=> Set[TState]
// for composing an eNFA transition with a NFA transition
implicit class RichPF(val f: eNFAtrans) extends AnyVal {
def +++(g: NFAtrans) : eNFAtrans =
{ case (q, None) => applyOrElse(f, (q, None))
case (q, Some(c)) =>
applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) }
}
// sequence of two NFAs
def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = {
val new_delta : eNFAtrans =
{ case (q, None) if enfa1.fins(q) => enfa2.starts }
eNFA(enfa1.starts, new_delta +++ enfa1.delta +++ enfa2.delta,
enfa2.fins)
}
// alternative of two NFAs
def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = {
val new_delta : NFAtrans = {
case (q, c) => applyOrElse(enfa1.delta, (q, c)) |
applyOrElse(enfa2.delta, (q, c)) }
val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q)
NFA(enfa1.starts | enfa2.starts, new_delta, new_fins)
}
// star of a NFA
def NFA_STAR(enfa: NFAt) : NFAt = {
val Q = TState()
val new_delta : eNFAtrans =
{ case (Q, None) => enfa.starts
case (q, None) if enfa.fins(q) => Set(Q) }
eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q))
}