1 // Thompson Construction (Part 2)

     2 

     3 // some more type 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 new_delta : NFAtrans = { 

    28     case (q, c) => applyOrElse(enfa1.delta, (q, c)) | 

    29                    applyOrElse(enfa2.delta, (q, c)) }

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

    31 

    32   NFA(enfa1.starts | enfa2.starts, new_delta, new_fins)

    33 }

    34 

    35 // star of a NFA

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

    37   val Q = TState()

    38   val new_delta : eNFAtrans = 

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

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

    41 

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

    43 }