Example of Minimization of Deterministic Finite Automata (DFA)
Minimization of DFA (Table Filling Method or Myhill-Nerode Theorem)
Steps:
- Draw a table for all pairs of states (P, Q)
- Mark all pairs where Pϵ F and Q∉F
- If there are any Unmarked pairs (P, Q) such that [δ(P, x),δ(Q, x)] is marked, then mark [P, Q] where ‘x’ is an input symbol. Repeat this until no more marking can be made.
- Combine all the unmarked pairs and make them a single state in the minimized DFA.
Example: Minimize the following DFA using Table Filling Method.
