Questions: DFA Properties and Minimization Algorithms

Question 1

In a DFA, states p and q are such that for every possible input string, both states lead to the same accept or reject outcome. What can you conclude?

• A. The states are distinguishable and must be kept separate
• B. The states are equivalent and can be merged without changing the language recognized
• C. Both states must be accepting states, since they produce the same outcomes
• D. The DFA is non-deterministic if two states behave identically

Answer: (B)

Two states are equivalent (and can be merged) if no string distinguishes them — no string w causes one state to accept while the other rejects. Merging equivalent states produces a smaller DFA recognizing the exact same language. Equivalent states don't have to both be accepting; two rejecting states can be equivalent if every suffix takes both to the same outcome. Determinism is unaffected by having equivalent states — the DFA is still deterministic, just redundant.

Question 2

Why is the uniqueness of the minimal DFA (up to isomorphism) a useful property?

• A. It guarantees that the minimization algorithm runs in polynomial time
• B. It allows two DFAs to be tested for language equivalence by minimizing both and comparing their structure
• C. It proves that all regular languages have the same number of states in their minimal DFA
• D. It means any DFA can be minimized by simply relabeling its states

Answer: (B)

Uniqueness provides a canonical form: for any regular language, there is exactly one minimal DFA (up to renaming of states). This means you can test whether two DFAs recognize the same language by minimizing both and checking if the results are structurally identical. No other computational model at the regular-language level has such a clean canonical form. This also provides a lower bound: if the minimal DFA has k states, no DFA can recognize the language with fewer.

Question 3

If two different DFAs both recognize the same regular language, their minimized forms will be isomorphic — identical up to the naming of states.

• T. True
• F. False

Answer: True

This is the uniqueness theorem for minimal DFAs: every regular language has exactly one minimal DFA, up to isomorphism (renaming of states). No matter how you construct two DFAs for the same language — different state names, different starting constructions — minimizing both will always produce structurally identical automata. This uniqueness is what makes the minimal DFA a canonical representative of the language and enables the language equivalence test.

Question 4

Two DFA states are equivalent if they were reached by the same set of input strings from the start state.

• T. True
• F. False

Answer: False

Equivalence is defined by future behavior, not past history. Two states are equivalent if, for every possible input string read from that point forward, both states produce the same accept/reject outcome. The strings that led to those states are irrelevant — what matters is what the automaton does from those states onward. This future-oriented definition is what makes the concept work: you can merge two states regardless of how they were reached, as long as they are indistinguishable by any suffix.

Question 5

What does it mean for two DFA states to be distinguishable, and why is distinguishability the basis for the minimization algorithm?

Model answer: Two states p and q are distinguishable if there exists some string w such that starting from p the DFA accepts w, but starting from q it rejects w (or vice versa). States not distinguishable by any string are equivalent and can be safely merged. Minimization works by finding all distinguishable pairs — starting from the obvious base case (accept vs. reject states are always distinguishable by the empty string) — and iteratively propagating distinguishability through the transition function until no new distinctions can be found. What remains unmarked are equivalent states that get merged.

The key insight is that 'equivalence' is purely about future behavior, making it independent of how states were designed or labeled. The base case is intuitive: an accepting and a rejecting state behave differently on the empty string. The iterative step propagates this: if states r and s are distinguishable, then any states p and q that transition to r and s respectively on input a are also distinguishable. This ensures every redundant state is identified before merging.