// DFAs

import scala.util._

abstract class State

type States = Set[State]

case class IntState(i: Int) extends State

object NewState {

  var counter = 0

  def apply() : IntState = {

    counter += 1;

    new IntState(counter - 1)

  }

}

// DFA class

case class DFA(states: States, 

               start: State, 

               delta: (State, Char) => State, 

               fins: States) {

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

    case Nil => q

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

  }

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

  def accepts(s: String) : Boolean = 

    Try(fins contains 

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

}

// example DFA from the lectures

val Q0 = NewState()

val Q1 = NewState()

val Q2 = NewState()

val Q3 = NewState()

val Q4 = NewState()

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

  case (Q0, 'a') => Q1

  case (Q0, 'b') => Q2

  case (Q1, 'a') => Q4

  case (Q1, 'b') => Q2

  case (Q2, 'a') => Q3

  case (Q2, 'b') => Q2

  case (Q3, 'a') => Q4

  case (Q3, 'b') => Q0

  case (Q4, 'a') => Q4

  case (Q4, 'b') => Q4

}

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

println(DFA1.accepts("aaa"))

println(DFA1.accepts("bb"))

println(DFA1.accepts("aaac"))