Automata (DFA,NFA,εNFA) in Scala

README.md

Automata in Scala is moved to https://github.com/everpeace/scalamata

TryAutomata.scala

/**
 * Automata (DFA,NFA,εNFA) in Scala
 * @author Shingo Omura <everpeace _at_ gmail _dot_ com>
 */
object TryAutomata extends App {

  // Set is equivalent to member ship function.
  implicit def set2func[E](set: Set[E]): E => Boolean = set.contains(_)

  // Automaton on alphabet  is equivalent to Seq[Σ] => (Boolean,Q)
  implicit def automaton2func[Q, Σ](a: Automaton[Q, Σ]): Seq[Σ] => (Boolean, Q) = a.accept(_)


  // Automaton
  trait Automaton[Q, Σ]{
    // return (isAccepted, final state)
    def accept(input: Seq[Σ]): (Boolean, Q)
  }

  // Deterministic Finite Automata
  // σ: transition function
  // q0: initial state
  // f: member ship function of accepted states
  case class DFA[Q, Σ](σ: (Q, Σ) => Q, q0: Q, f: Q => Boolean) extends Automaton[Q, Σ]{

    def accept(input: Seq[Σ]): (Boolean, Q) = _accept(input)(q0)

    private def _accept(input: Seq[Σ])(q: Q): (Boolean, Q) = input match {
      case x :: xs => _accept(xs)(σ(q, x))
      case _ => (f(q), q)
    }

    // cartesian product of automata
    def ×[_Q, _Σ](another: DFA[_Q, _Σ]): DFA[(Q, _Q), (Σ, _Σ)]
    = DFA[(Q, _Q),(Σ, _Σ)]((q, x) => (this.σ(q._1, x._1), another.σ(q._2, x._2)),
                           (this.q0, another.q0),
                           q => this.f(q._1) && another.f(q._2))

  }

  // alphabet
  sealed abstract class Alpha
  case object A extends Alpha
  case object B extends Alpha

  // DFA which accept *AB
  // +-B-↓       +-A -+
  // +-> Q0 --A--+>Q1 + ---B--> Q2
  //     ↑         ↑------A-----+
  //     ↑----------------B-----+
  sealed abstract class State1
  case object Q0 extends State1
  case object Q1 extends State1
  case object Q2 extends State1
  val σ1: (State1, Alpha) => State1
  = {
     case (Q0, A) => Q1
     case (Q0, B) => Q0
     case (Q1, A) => Q1
     case (Q1, B) => Q2
     case (Q2, A) => Q1
     case (Q2, B) => Q0
  }
  val _ABinDFA = DFA(σ1, Q0, Set[State1](Q2))

  // [output]
  // (true,Q2)
  // (false,Q0)
  println("DFA on {A,B}* which accepts *AB")
  println("input:"+Seq(A,B)+"=>"+_ABinDFA.accept(Seq(A,B)))
  println("input:"+Seq(A,A,A,B)+"=>"+_ABinDFA.accept(Seq(A,A,A,B)))
  // automata is equivalent to functions from Seq to (Boolean,State)
  println("input:"+Seq(A,B,A)+"=>"+_ABinDFA(Seq(A,B,A)))
  println("input:"+Seq(A,B,B,B)+"=>"+_ABinDFA(Seq(A,B,B,B)))

  // cartesian product of automata
  // [output]
  // (true,(Q2,Q2))
  println("\nDFA on ({A,B},{A,B})* which accepts *(A,A)(B,B)")
  println("input:"+Seq(A, A, B).zip(Seq(A, A, B))+"=>"+(_ABinDFA × _ABinDFA)(Seq(A, A, B).zip(Seq(A, A, B))))




  // Non Deterministic Finite Automata without ε-transition
  // σ: non deterministic transition function
  // q0: initial state
  // f: member ship function of accepted states.
  case class NFA[Q, Σ](σ: (Q, Σ) => Set[Q], q0: Q, f: Q => Boolean) extends Automaton[Set[Q], Σ]{
    // simulated by deterministic automata
    def accept(input: Seq[Σ]) = toDFA.accept(input)

    def toDFA = DFA[Set[Q],Σ]((qs, input) => qs.flatMap(σ(_, input)), // to state is unioned.
                              Set(q0),                                // initial state is {q0}
                              _.exists(f))                            // accepted if states contains f.
  }

  // Sample of NFA which accepts *AB.
  //  +----> Q3 --A--> Q4 --B-->Q5
  //  +-A,B--+
  sealed class State2
  case object Q3 extends State2
  case object Q4 extends State2
  case object Q5 extends State2
  val σ2: (State2, Alpha) => Set[State2]
  = {
    case (Q3, A)=> Set(Q3,Q4)
    case (Q3, B)=> Set(Q3)
    case (Q4, B)=> Set(Q5)
    case _=> Set.empty
  }
  val _ABinNFA = NFA(σ2,Q3,Set[State2](Q5))

  //[output]:
  // (true,Set(Q3,Q5))
  // (true,Set(Q3,Q5))
  // (false,Set(Q3,Q4))
  // (false,Set(Q3))
  println("\nNFA on {A,B}* which accepts *AB")
  println("input:"+Seq(A,B)+"=>"+_ABinNFA.accept(Seq(A,B)))
  println("input:"+Seq(A,A,A,B)+"=>"+_ABinNFA.accept(Seq(A,A,A,B)))
  println("input:"+Seq(A,B,A)+"=>"+_ABinNFA.accept(Seq(A,B,A)))
  println("input:"+Seq(A,B,B,B)+"=>"+_ABinNFA.accept(Seq(A,B,B,B)))





  // Non Deterministic Finate Automata with ε-transitions
  // σ: transition function with ε-transition ( as partial function)
  // q0: initial state
  // f: member ship function of accepted states
  sealed trait ε
  object ε extends ε // empty alphabet
  case class εNFA[Q,Σ](σ:PartialFunction[(Q, Either[Σ, ε]),Set[Q]],q0:Q, f:Q=>Boolean) extends Automaton[Set[Q],Σ]{
    // convert to NFA without ε-transition by eliminating ε-transition
    def accept(input: Seq[Σ]) = toNFA.accept(input)

    def toNFA = {
      val _σ:(Q, Σ)=>Set[Q] = (q,x) =>{
        val σ_f = σ.orElse({ case _ => Set.empty[Q]}:PartialFunction[(Q, Either[Σ, ε]),Set[Q]])
        val normal_trans = σ_f(q,Left(x))
        val ε_bipassed = εClosure(q).flatMap(σ_f(_,Left(x)))
        normal_trans ++ ε_bipassed
      }
      val _f: Q => Boolean = q => f(q) || (εClosure(q) exists f)
      NFA(_σ,q0,_f)
    }

    def toDFA = toNFA.toDFA

    private def εClosure(q:Q):Set[Q] = {
      val σ_f = σ orElse ({case _=> Set.empty[Q]}:PartialFunction[(Q, Either[Σ, ε]),Set[Q]])
      var visited = Set.empty[Q]
      val queue = new scala.collection.mutable.Queue[Q]()
      queue.enqueue(q)
      while(!queue.isEmpty){
        val new_neighbors = σ_f(queue.dequeue(),Right(ε)) -- visited
        queue ++= new_neighbors
        visited ++= new_neighbors
      }
      visited
    }
  }

  // ε-NFA sample which only accepts A+
  // Q6 --A--> Q7
  //  ↑----ε---+
  sealed abstract class State3
  case object Q6 extends State3
  case object Q7 extends State3

  val σ3:PartialFunction[(State3, Either[Alpha, ε]),Set[State3]] ={
    case (Q6, Left(A)) => Set(Q7)
    case (Q7,Right(ε)) => Set(Q6)
  }
  val Aplus = εNFA(σ3,Q6,Set[State3](Q7))
  
  //[output]
  // (false,Set(Q6))
  // (true,Set(Q7))
  // (false,Set())
  println("\nε-NFA on {A,B}* which only accepts A+:")
  println("input:"+Seq()+"=>"+Aplus(Seq()))
  println("input:"+Seq(A,A)+"=>"+Aplus(Seq(A,A)))
  println("input:"+Seq(B)+"=>"+Aplus(Seq(B)))
}