CODEWITHSUNDEEP
infinitedfa
user1198722
user1198722

Reputation:

The number of DFA accept same language is countably infinite

I realize that the DFA is countable since the DFA for specific language is the subset of all DFAs. Just wonder how to prove that the number of DFAs accept specific language is infinite?

Upvotes: 1

Views: 2104

Answers (1)

Patrick87
Patrick87

Reputation: 28302

Take any DFA for your language. It must contain some other cycle/loop. Add a new set of states corresponding to the cycle, and allow this set of states to represent odd-numbered passes through the cycle/loop (the original states represent even passes). If necessary, add nondeterminism and use the powerset construction to turn the NFA back into a DFA.

Either way, you end up with a DFA for the same language that has more states.

Upvotes: 2

Related Questions