Minimization of the deterministic finite automaton (DFA) using Moore's algorithm in C++

dfa_minimization.cpp

#include <iostream>
#include <utility>
#include <vector>
#include <set>
#include <cassert>

class DFA {
  public:
  DFA(int n, int z, std::set<int> f, std::vector<std::vector<int>> _delta) :
  N(n), Z(z), F(std::move(f)), delta(std::move(_delta)) {
    // validity check
    for (int i: F) { assert(i < N); }
    assert(delta.size() == N);
    for (const auto& a: delta) {
      assert(a.size() == Z);
      for (const int i: a) { assert(i < N); }
    }
  };
  int N;  // number of internal states
  int Z;  // number of alphabets
  std::set<int> F;  // set of final states
  std::vector< std::vector<int> > delta; // state-transition function.
  // represented by NxZ two-dim vector. delta[q][s] = transition from state-q by input s
};

bool Equivalent(const DFA& dfa, int i, int j, const std::vector<int>& partition_0) {
  for (int z = 0; z < dfa.Z; z++) {  // for input z
    int dest_i = dfa.delta[i][z];
    int dest_j = dfa.delta[j][z];
    if (partition_0[dest_i] != partition_0[dest_j]) return false;
  }
  return true;
}

std::vector<int> Minimize(const DFA& dfa) {
  const int N = dfa.N;

  std::vector<int> partition_0(N, -1);
  // initialize grouping by the final state
  int accept_idx = *dfa.F.begin(), reject_idx = -1;
  for (int i: dfa.F) {
    partition_0[i] = accept_idx;
  }
  for (int i = 0; i < N; i++) {
    if (partition_0[i] < 0) {
      if (reject_idx < 0) reject_idx = i;
      partition_0[i] = reject_idx;
    }
  }

  while (true) {
    std::vector<int> partition(N, -1);
    int i = 0;
    while (i < N) {
      partition[i] = i;
      int i_next = N;
      for (int j = i+1; j < N; j++) {
        if (partition[j] >= 0) continue;  // skip if j is already merged
        if (partition_0[i] == partition_0[j] && Equivalent(dfa, i, j, partition_0)) {
          partition[j] = i;   // merge i & j
        }
        else if (i_next == N) { i_next = j; }  // keep the first unmerged node
      }
      i = i_next;
    }
    if (partition_0 == partition) break;
    partition_0 = partition;
  }

  return partition_0;
}

int main(int argc, char* argv[]) {
  DFA dfa1(6, 2, {2,3,4}, {{1,2}, {0,3}, {4,5}, {4,5}, {4,5}, {5,5}});
  auto m1 = Minimize(dfa1);
  std::vector<int> ans = { 0,0,2,2,2,5 };
  for (auto x: m1) {
    std::cerr << x << ", ";
  }
  assert(m1 == ans);

  return 0;
}

In the main function, the following DFA is minimized.

https://en.wikipedia.org/wiki/DFA_minimization#/media/File:DFA_to_be_minimized.jpg

The minimized representation is the following:

https://en.wikipedia.org/wiki/DFA_minimization#/media/File:Minimized_DFA.jpg

shahbash