Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
I suspect a trick question in the material you are studying - there are no DFAs with an infinite number of states in the first place.
in fact, the whole point of D/NFAs is their finiteness. if you could have an inifinite number of (reachable) states in your NFA you'd actually be able to recognize any language; just take for every word in your language the trivial deterministic recognizer and connect a global start state with $\lambda$-transitions to the start state of each of these automata.
You can certainly add as many disconnected states as you want. However, I think that the definition of DFA or NFA stipulates that the number of states is finite (that is what the F stands for). So it would not be a DFA. However, even with an infinity of states, it can certainly recognize a regular language, if appropriately built (as you suggest, for example).
The reason why the definition stipulates a finite number of states is that an infinite number of states will allow you to recognize about anything. After all, a Turing Machine is an automaton just like the DFA, but with an infinite number of states, that you can actually enumerate, as you can enumerate the transitions (also infinite in number).
I have not looked at it previously, but I believe that you can actually do much better than Turing Machine with a DIA (Deterministic Infinite Automaton). You have only countably many TM, but you have continuously many DIAs, as many as you have real numbers. So I should expect that they would do things one does not even expect from TM.
On the other hand, anything they do, they will do in finite number of steps, so that remains a limitation (as compared to Zeno machines, or machines using looping time-lines). I did not see anything in a fast look on the hypercomputation page of wikipedia.
I am sure someone has worked on continuous machines (I do not dare call them real machines, real numbers are enough of an abusive claim). Maybe looking at work on computable reals, and related literature can put some light on this.
They can solve the halting problem for ordinary TM. You just follow the usual diagonalization construction that describe a solution for the halting problem. Since you do not require that construction to be describable by an ordinary Turing Machine, there is no contradiction. Isn't this a happy world?
The only difficulty, albeit a minor one, is that we do not know how to implement them. Miracles are not of this world.. . yet.
