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
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 ?
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.
Check the definition. It usually goes like $M = (Q, \Sigma, \delta, q_0, F)$, with $Q$ a finite set of states, $\Sigma$ the (input) alphabet, $\delta \colon Q \times \Sigma \to Q$ the transition function, $q_0 \in Q$ the initial state, $F \subseteq Q$ the set of final (accepting) states. Note that the only condition on $\delta$ is it being a function. To exclude "nonsense" like unreachable states would complicate the definition enormously, and force complex pŕoofs to otherwise quite elegant constructions (like the subset construction for NFA to DFA, where you just declare all subsets of states of the NFA as states of the DFA -- often the vast majority of the subsets are impossible).
Most mathematical definitions are given in such a way as to capture what is relevant and make the concept easy to work with, perhaps allowing nonsense that doesn't hurt. Simplicity (of proofs) is key.
