Skip to content

Instantly share code, notes, and snippets.

Created March 27, 2012 08:39
Show Gist options
  • Save everpeace/2214051 to your computer and use it in GitHub Desktop.
Save everpeace/2214051 to your computer and use it in GitHub Desktop.
Automata (DFA,NFA,εNFA) in 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")
// automata is equivalent to functions from Seq to (Boolean,State)
// 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))
// (true,Set(Q3,Q5))
// (true,Set(Q3,Q5))
// (false,Set(Q3,Q4))
// (false,Set(Q3))
println("\nNFA on {A,B}* which accepts *AB")
// 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)
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]()
val new_neighbors = σ_f(queue.dequeue(),Right(ε)) -- visited
queue ++= new_neighbors
visited ++= new_neighbors
// ε-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))
// (false,Set(Q6))
// (true,Set(Q7))
// (false,Set())
println("\nε-NFA on {A,B}* which only accepts A+:")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment