1 // eNFA that does not accept any string

     2 def eNFA_ZERO(): NFA[TState, Char] = {

     3   val Q = TState()

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

     5 }

     6 

     7 // eNFA that accepts the empty string

     8 def eNFA_ONE() : NFA[TState, Char] = {

     9   val Q = TState()

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

    11 }

    12 

    13 // eNFA that accepts the string "c"

    14 def eNFA_CHAR(c: Char) : NFA[TState, Char] = {

    15   val Q1 = TState()

    16   val Q2 = TState()

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

    18 }

    19 

    20 // alternative of two eNFAs

    21 def eNFA_ALT(enfa1: NFA[TState, Char], enfa2: NFA[TState, Char]) : NFA[TState, Char] = {

    22   val Q = TState()

    23   val new_delta : eNFAtrans = 

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

    25 

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

    27 

    28   eNFA(Set(Q), 

    29        new_delta andAlso enfa1.delta andAlso enfa2.delta, 

    30        new_fins)

    31 }

    32 

    33 // sequence of two eNFAs

    34 def eNFA_SEQ(enfa1: NFA[TState, Char], enfa2: NFA[TState, Char]) : NFA[TState, Char] = {

    35   val new_delta : eNFAtrans = 

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

    37   

    38   eNFA(enfa1.starts, 

    39        new_delta andAlso enfa1.delta andAlso enfa2.delta, 

    40        enfa2.fins)

    41 }

    42 

    43 // star of an eNFA

    44 def eNFA_STAR(enfa: NFA[TState, Char]) : NFA[TState, Char] = {

    45   val Q = TState()

    46   val new_delta : eNFAtrans = 

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

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

    49 

    50   eNFA(Set(Q), new_delta andAlso enfa.delta, Set(Q))

    51 }