1 // DFAs

     2 import scala.util._

     3 

     4 abstract class State

     5 type States = Set[State]

     6 

     7 case class IntState(i: Int) extends State

     8 

     9 object NewState {

    10   var counter = 0

    11   

    12   def apply() : IntState = {

    13     counter += 1;

    14     new IntState(counter - 1)

    15   }

    16 }

    17 

    18 

    19 // DFA class

    20 case class DFA(states: States, 

    21                start: State, 

    22                delta: (State, Char) => State, 

    23                fins: States) {

    24   

    25   def deltas(q: State, s: List[Char]) : State = s match {

    26     case Nil => q

    27     case c::cs => deltas(delta(q, c), cs) 

    28   }

    29   

    30   // wether a string is accepted by the automaton or not

    31   def accepts(s: String) : Boolean = 

    32     Try(fins contains 

    33       (deltas(start, s.toList))) getOrElse false

    34 }

    35 

    36 

    37 // example DFA from the lectures

    38 val Q0 = NewState()

    39 val Q1 = NewState()

    40 val Q2 = NewState()

    41 val Q3 = NewState()

    42 val Q4 = NewState()

    43 

    44 

    45 val delta : (State, Char) => State = {

    46   case (Q0, 'a') => Q1

    47   case (Q0, 'b') => Q2

    48   case (Q1, 'a') => Q4

    49   case (Q1, 'b') => Q2

    50   case (Q2, 'a') => Q3

    51   case (Q2, 'b') => Q2

    52   case (Q3, 'a') => Q4

    53   case (Q3, 'b') => Q0

    54   case (Q4, 'a') => Q4

    55   case (Q4, 'b') => Q4

    56 }

    57 

    58 val DFA1 = DFA(Set(Q0, Q1, Q2, Q3, Q4), Q0, delta, Set(Q4))

    59 

    60 println(DFA1.accepts("aaa"))

    61 println(DFA1.accepts("bb"))

    62 println(DFA1.accepts("aaac"))

    63 

    64