progs/display/thompson2.scala
author Christian Urban <urbanc@in.tum.de>
Sun, 07 May 2017 03:01:29 +0100
changeset 489 e28d7a327870
parent 488 598741d39d21
permissions -rw-r--r--
updated

// 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))
}