1 // Thompson Construction (Part 1)

     2 // (needs  :load nfa.scala

     3 //         :load enfa.scala)

     4 

     5 

     6 // states for Thompson construction

     7 case class TState(i: Int) extends State

     8 

     9 object TState {

    10   var counter = 0

    11   

    12   def apply() : TState = {

    13     counter += 1;

    14     new TState(counter - 1)

    15   }

    16 }

    17 

    18 

    19 // some types abbreviations

    20 type NFAt = NFA[TState, Char]

    21 

    22 

    23 // NFA that does not accept any string

    24 def NFA_ZERO(): NFAt = {

    25   val Q = TState()

    26   NFA(Set(Q), { case _ => Set() }, Set())

    27 }

    28 

    29 // NFA that accepts the empty string

    30 def NFA_ONE() : NFAt = {

    31   val Q = TState()

    32   NFA(Set(Q), { case _ => Set() }, Set(Q))

    33 }

    34 

    35 // NFA that accepts the string "c"

    36 def NFA_CHAR(c: Char) : NFAt = {

    37   val Q1 = TState()

    38   val Q2 = TState()

    39   NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))

    40 }