// Thompson Construction (Part 2)

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 Q = TState()

  val new_delta : eNFAtrans = 

    { case (Q, None) => enfa1.starts | enfa2.starts }

  val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q)

  eNFA(Set(Q), new_delta +++ enfa1.delta +++ enfa2.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))

}