patternMinor
Do all states in a DFA must be connected?
Viewed 0 times
dfamustallstatesconnected
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#23127, answer score: 4
Revisions (0)
No revisions yet.