11
$\begingroup$

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 enter image description here

So my question is , are we allowed to have such a state in a DFA ?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Read any definition of a FA and you'll almost certainly find that it allows unreachable states. $\endgroup$ – Rick Decker Jan 16 '20 at 16:11
  • $\begingroup$ Where does that statement come from? Does the source have some idiosyncratic definition of "complete DFA"? $\endgroup$ – rici Jan 16 '20 at 17:27
  • $\begingroup$ The question would benefit, at least, from a definition of $L(A)$, or even better, from a more complete definition of $A$ too. $\endgroup$ – bracco23 Jan 17 '20 at 7:56
14
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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