Example 3
Minimization of DFA with unreachable state using Myhill Nerode Theorem - Table Filling Method
Step 1 Draw a table for all pairs of states (P, Q) not necessarily connected
directly [All are unmarked initially]
Step 2 Consider every state pair (P, Q) in the DFA where P ∈ F and Q ∉ F or vice versa and mark them. [Here F is the set of final states]
Step 3 Repeat this step until we cannot mark anymore states:
If there is an unmarked pair (P, Q), mark it if the pair {δ(P, A), δ (Q, A)} is marked for some input alphabet.
Step 4 Combine all the unmarked pair (P, Q) and make them a single state in the reduced DFA.
Comments
Post a Comment