// a class for deterministic finite automata,

// the type of states is kept polymorphic

case class Automaton[A](start: A, states: Set[A], delta: Map[(A, Char), A], fins: Set[A]) {

  // the transition function lifted to list of characters

  def deltas(q: A, cs: List[Char]) : A = 

    if (states.contains(q)) cs match {

      case Nil => q

      case c::cs => 

        if (delta.isDefinedAt(q, c)) deltas(delta(q, c), cs)

        else throw new RuntimeException(q + " does not have a transition for " + c)

    }

    else throw new RuntimeException(q + " is not a state of the automaton")

  // wether a string is accepted by the automaton

  def accepts(s: String) = 

    try {

      fins.contains(deltas(start, s.toList))

    } catch {

      case e:RuntimeException => false

    }

}

abstract class Rexp

case object NULL extends Rexp

case object EMPTY extends Rexp

case class CHAR(c: Char) extends Rexp 

case class ALT(r1: Rexp, r2: Rexp) extends Rexp

case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 

case class STAR(r: Rexp) extends Rexp

implicit def string2rexp(s : String) = { 

  def chars2rexp (cs: List[Char]) : Rexp = cs match {

    case Nil => EMPTY

    case c::Nil => CHAR(c)

    case c::cs => SEQ(CHAR(c), chars2rexp(cs))

  }

  chars2rexp(s.toList)

}

def nullable (r: Rexp) : Boolean = r match {

  case NULL => false

  case EMPTY => true

  case CHAR(_) => false

  case ALT(r1, r2) => nullable(r1) || nullable(r2)

  case SEQ(r1, r2) => nullable(r1) && nullable(r2)

  case STAR(_) => true

}

def der (r: Rexp, c: Char) : Rexp = r match {

  case NULL => NULL

  case EMPTY => NULL

  case CHAR(d) => if (c == d) EMPTY else NULL

  case ALT(r1, r2) => ALT(der(r1, c), der(r2, c))

  case SEQ(r1, r2) => if (nullable(r1)) ALT(SEQ(der(r1, c), r2), der(r2, c))

                      else SEQ(der(r1, c), r2)

  case STAR(r) => SEQ(der(r, c), STAR(r))

}

// Here we construct an automaton whose

// states are regular expressions

type State = Rexp

type States = Set[State]

type Transition =  Map[(State, Char), State]

def goto(q: State, c: Char, qs: States, delta: Transition) : (States, Transition) = {

  val qc : State = der(q, c)

  if (qs.contains(qc)) (qs, delta + ((q, c) -> q))

  else explore(qs + qc, delta + ((q, c) -> qc), qc)

}

// we use as alphabet all lowercase letters

val alphabet = "abcdefghijklmnopqrstuvwxyz".toSet

def explore (qs: States, delta: Transition, q: State) : (States, Transition) =

  alphabet.foldRight[(States, Transition)] (qs, delta) ((c, qsd) => goto(q, c, qsd._1, qsd._2)) 

def mk_automaton (r: Rexp) : Automaton[Rexp] = {

  val (qs, delta) = explore(Set(r), Map(), r);

  val fins = for (q <- qs if nullable(q)) yield q;

  Automaton[Rexp](r, qs, delta, fins)

}

val A = mk_automaton(ALT("ab","ac"))

println(A.accepts("bd"))

println(A.accepts("ab"))

println(A.accepts("ac"))