// 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"))