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
