DFA util

dfa.d

import std.stdio;
import std.typecons;
import std.conv;

class DFA(Q, Sigma) {
  Q q0;
  Q[] F;
  Q[Tuple!(Q, Sigma)] delta;

  this(Q[Tuple!(Q, Sigma)] delta, Q q0, Q[] F) {
    this.delta = delta;
    this.q0 = q0;
    this.F = F;
  }

  bool accept(Sigma[] input) {
    Q t = q0;
    foreach (s; input) {
      Tuple!(Q, Sigma) tp = tuple(t, s);
      if (tp !in delta) {
        return false;
      }
      //writefln("t: %s, tp: %s, nt: %s", t, tp, delta[tp]);

      t = delta[tp];
    }

    import std.algorithm;
    return F.any!(f => f == t);
  }
}

interface State {}
class A : State {} class B : State {}
class C : State {} class D : State {}
class E : State {} class F : State {}
class G : State {}

void main() {
  auto a = new A; auto b = new B;
  auto c = new C; auto d = new D;
  auto e = new E; auto f = new F;
  auto g = new G;

  auto dfa = new DFA!(State, char)(
      [
        tuple(a.to!State, 'a') : b, tuple(a.to!State, 'b') : c, tuple(a.to!State, 'c') : a,
        tuple(b.to!State, 'a') : c, tuple(b.to!State, 'b') : d, tuple(b.to!State, 'c') : b, 
        tuple(c.to!State, 'a') : d, tuple(c.to!State, 'b') : e, tuple(c.to!State, 'c') : c,
        tuple(d.to!State, 'a') : e, tuple(d.to!State, 'b') : e, tuple(d.to!State, 'c') : g,
        tuple(e.to!State, 'a') : e, tuple(e.to!State, 'b') : e, tuple(e.to!State, 'c') : e,
        tuple(g.to!State, 'a') : e, tuple(g.to!State, 'b') : e, tuple(g.to!State, 'c') : g,
      ].to!(State[Tuple!(State, char)]),
      a,
      [g]);

  char[][] test_cases = [
    "aaac".to!(char[]),
    "abc".to!(char[]),
    "abb".to!(char[]),
    "abca".to!(char[]),
  ];

  foreach (test_case; test_cases) {
    writefln("%s -> %s", test_case, dfa.accept(test_case));
  }
}