patternModerate
Can a DFA have an unreachable state?
Viewed 0 times
candfaunreachablestatehave
Problem
I am trying to prove or disprove the following statement:
If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$
So my initial thinking is to find a counter example. If say we were to construct a DFA with one accepting state, and that state is never reached then the proposition is false.
For instance :
Assume we have the following automaton
So my question is , are we allowed to have such a state in a DFA ?
If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$
So my initial thinking is to find a counter example. If say we were to construct a DFA with one accepting state, and that state is never reached then the proposition is false.
For instance :
Assume we have the following automaton
So my question is , are we allowed to have such a state in a DFA ?
Solution
You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models).
You may wonder what is the point of having them, given that they are unreachable and have no effect on the language.
Well, automata are typically not designed by hand. Rather, they are usually obtained algorithmically by translation from other types of specifications, models, etc.
These translation algorithms often don't guarantee that there are no unreachable states, and very often there are many unreachable states.
For example, take the subset construction, that transforms an NFA to an equivalent DFA. There are typically many unreachable states in the naive construction (although it can be optimized to construct only the reachable states).
However, there are other constructions that are much more involved (e.g., the translation of Linear Temporal Logic to Nondeterministic Buechi automata).
In fact, one of the most fundamental algorithms on automata is that of emptiness -- check whether the language is empty. To do so, we look for a reachable accepting state. If automata only had reachable states, we would only have to check whether there are accepting states, but this is not enough.
Finally, I'll remark that this algorithm is often symbolic, in that you don't run it on an explicit automaton, but on a symbolic representation. For example, you can check emptiness of a DFA constructed by determinizing an NFA without actually contstructing the whole thing.
You may wonder what is the point of having them, given that they are unreachable and have no effect on the language.
Well, automata are typically not designed by hand. Rather, they are usually obtained algorithmically by translation from other types of specifications, models, etc.
These translation algorithms often don't guarantee that there are no unreachable states, and very often there are many unreachable states.
For example, take the subset construction, that transforms an NFA to an equivalent DFA. There are typically many unreachable states in the naive construction (although it can be optimized to construct only the reachable states).
However, there are other constructions that are much more involved (e.g., the translation of Linear Temporal Logic to Nondeterministic Buechi automata).
In fact, one of the most fundamental algorithms on automata is that of emptiness -- check whether the language is empty. To do so, we look for a reachable accepting state. If automata only had reachable states, we would only have to check whether there are accepting states, but this is not enough.
Finally, I'll remark that this algorithm is often symbolic, in that you don't run it on an explicit automaton, but on a symbolic representation. For example, you can check emptiness of a DFA constructed by determinizing an NFA without actually contstructing the whole thing.
Context
StackExchange Computer Science Q#119607, answer score: 14
Revisions (0)
No revisions yet.