Skip to content

Instantly share code, notes, and snippets.

@yohm
Last active March 25, 2024 15:21
Show Gist options
  • Save yohm/aff118fd11b6d2e8d6e565756f9c92d6 to your computer and use it in GitHub Desktop.
Save yohm/aff118fd11b6d2e8d6e565756f9c92d6 to your computer and use it in GitHub Desktop.
Minimization of the deterministic finite automaton (DFA) using Moore's algorithm in C++
#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;
}
@yohm
Copy link
Author

yohm commented Nov 27, 2021

@muhammad-shahzab
Copy link

shahbash

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment