[Solved]: Do all states in a DFA must be connected?

Problem Detail: 

Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal?

I'm studying for a test, and I found a question that asks if an infinite DFA could represent a regular language, and I want to use a regular DFA and add all the infinite states not connected to the original. Can I do that?

Asked By : Algosub

Answered By : Yuval Filmus

As babou mentions, infinite deterministic automata are rather powerful. In fact, they can compute all languages. Consider the "universal deterministic automaton" which is a $|\Sigma|$-ary infinite tree, with one state per each string in $\Sigma^*$. By choosing the set of accepting states to be $L \subseteq \Sigma^*$, we obtain an automaton which accepts $L$.

Regarding connectedness, while a DFA need not be connected, every disconnected DFA is equivalent to a smaller one which is connected; the minimal DFA is always connected.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23127