1 // Thompson Construction (Part 2)

     2 

     3 // some more types abbreviations

     4 type NFAtrans = (TState, Char) :=> Set[TState]

     5 type eNFAtrans = (TState, Option[Char]) :=> Set[TState]

     6 

     7 

     8 // for composing an eNFA transition with a NFA transition

     9 implicit class RichPF(val f: eNFAtrans) extends AnyVal {

    10   def +++(g: NFAtrans) : eNFAtrans = 

    11   { case (q, None) =>  applyOrElse(f, (q, None)) 

    12     case (q, Some(c)) => 

    13       applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c))  }

    14 }

    15 

    16 // sequence of two NFAs

    17 def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = {

    18   val new_delta : eNFAtrans = 

    19     { case (q, None) if enfa1.fins(q) => enfa2.starts }

    20   

    21   eNFA(enfa1.starts, new_delta +++ enfa1.delta +++ enfa2.delta, 

    22        enfa2.fins)

    23 }

    24 

    25 // alternative of two NFAs

    26 def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = {

    27   val Q = TState()

    28   val new_delta : eNFAtrans = 

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

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

    31 

    32   eNFA(Set(Q), new_delta +++ enfa1.delta +++ enfa2.delta, 

    33        new_fins)

    34 }

    35 

    36 // star of a NFA

    37 def NFA_STAR(enfa: NFAt) : NFAt = {

    38   val Q = TState()

    39   val new_delta : eNFAtrans = 

    40     { case (Q, None) => enfa.starts

    41       case (q, None) if enfa.fins(q) => Set(Q) }

    42 

    43   eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q))

    44 }