04 - Minimization of DFA, Table Filling Method or Myhill-Nerode Theorem in C++ 1/3

We will implement Minimization of DFA or Deterministic Finite Automata using Table Filling Method or Myhill-Nerode Theoream.

03 - C++ Library for Deterministic Finite Automata (DFA), Nondeterministic Finite Automata (NFA)

Minimization of DFA - Table Filling Method (Myhill-Nerode Theorem)

STEP 1. Draw a table for all pairs of states (P, Q)
STEP 1-1. Collect all states
STEP 1-2. Build state pairs
STEP 2. Mark all pairs where P is in F and Q is NOT in F
STEP 3. If there are any Unmarked pairs (P, Q)
such that [delta(P,x), delta(Q, x)] is Marked,
then mark[P, Q], where 'x' an input symbol.
Repeat this until no nore markings can be made.
STEP 4. Combine all the Unmarked pairs
and make them a single state in the minimized DFA
STEP 5. Create new states for Minimized DFA
STEP 6. Create Minimized DFA with new states

004 - Subset Construction in C/C++, How to Enumerate Subsets

How to Enumerate Combinations or Construct Subsets in C++

Minimization of DFA - Table Filling Method (Example)

Download source Code: