1 // Thompson Construction (Part 1)

     2 // (needs  :load dfa.scala

     3 //         :load nfa.scala

     4 //         :load enfa.scala)

     5 

     6 

     7 // states for Thompson construction

     8 case class TState(i: Int) extends State

     9 

    10 object TState {

    11   var counter = 0

    12   

    13   def apply() : TState = {

    14     counter += 1;

    15     new TState(counter - 1)

    16   }

    17 }

    18 

    19 

    20 // a type abbreviation

    21 type NFAt = NFA[TState, Char]

    22 

    23 

    24 // a NFA that does not accept any string

    25 def NFA_ZERO(): NFAt = {

    26   val Q = TState()

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

    28 }

    29 

    30 // a NFA that accepts the empty string

    31 def NFA_ONE() : NFAt = {

    32   val Q = TState()

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

    34 }

    35 

    36 // a NFA that accepts the string "c"

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

    38   val Q1 = TState()

    39   val Q2 = TState()

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

    41 }