Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Sure, states don't need to be reachable. Of course, you could accomplish the same thing by (a) having no accepting states (the empty language is regular) or (b) replacing a dead state with a dead "trail" that goes on forever or (c) defining the DFA to be an infinite $|\Sigma|$-ary tree where a node is accepting if it's in your target languages. With infinitely many states, it's pretty easy to accept anything you want. –  Patrick87 Mar 27 at 13:53
    
Yes, that would be fine. –  David Richerby Mar 27 at 14:16
1  
Still, it seems a bit contradictory to disconnect a state for a wired reason. –  babou Mar 27 at 14:57
3  
You have a formal definition. Read it, understand it and answer the question yourself. That said, the notion "infinite deterministic finite automaton" does not make a lot of sense. Also, you can have infinitely many states, all reachable, and the described language is still regular. –  Raphael Mar 27 at 15:14
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
A small point: I wouldn't call the class of automata with infinitely many states "continuous" since continuity is a quite different property, related to the behaviour of functions. Each individual automaton would be countable; there would just be uncountably many of them. –  David Richerby Mar 27 at 16:04
1  
@DavidRicherby Thanks. I agree. Actually I called them DIA, or NIA while I am at it. I meant to say Continuum rather than Continuous. It happens to be the same word in my native language. I was referring to cardinality. I will change that in the next edit. –  babou Mar 27 at 16:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.