# If DFA has two states, which of the conditions hold?

Let $$L$$ be a regular language ,and $$M = (Q, Σ, δ, q_0, A)$$ is a DFA such that $$L(M) = L$$.
Prove that if $$|Q| = 2$$ then one of the following holds :
a) $$L=∅$$ b) $$ε∈L$$ c) $$∃a∈Σ$$ and $$a∈L$$

The problem is, I think all of these are FALSE. If there is 2 states, none of them are accepting states, then L will have no elements. This disproves b) and c). However if one of the states is accepting, then a) is false ! I dont see how one of these statements is always true.

• Without further restrictions, I agree with you – siracusa Sep 30 '19 at 6:44
• If none of the states is accepting, it’s case a. If the initial state is accepting, it’s case b. If the other state is accepting, it’s case c if the state is reachable, and case a otherwise. – Yuval Filmus Sep 30 '19 at 7:28
• At least one of the three statements will be true. But note that (b) and (c) can both be true at the same time. – gandalf61 Sep 30 '19 at 11:06
• Also note that "one of the following holds" means that at least one of the three statements is true for any given two-state DFA, but a different statement (or statements) may be true for different DFAs. – gandalf61 Sep 30 '19 at 11:13
• More generally, the proof of the pumping lemma shows that if a DFA with $n$ steps accepts some word, then it accepts a word whose length is shorter than $n$. – Yuval Filmus Sep 30 '19 at 15:22

You seem to be misunderstanding the statement of the exercise. It wants you to show that if $$L$$ is a language accepted by a DFA containing two states, then either $$L$$ is empty, or $$L$$ contains the empty word, or $$L$$ contains a word of length 1. Which of the cases holds depends on $$L$$. More explicitly:

• If no state of the DFA is accepting, then $$L = \emptyset$$.
• If the initial state of the DFA is accepting, then $$\epsilon \in L$$.
• If the other state of the DFA is accepting, then either the state is reachable, in which case $$\sigma \in L$$ for some $$\sigma \in \Sigma$$, or else it is unreachable, in which case $$L = \emptyset$$.

More generally, the proof of the pumping lemma shows that if $$L$$ is accepted by a DFA containing $$n$$ states, then either $$L = \emptyset$$ or $$L$$ contains some word whose length is less than $$n$$. This is sharp, in the following sense: for each $$n \geq 1$$ and $$m \in \{0,\ldots,n-1\}$$, there is a language accepted by a DFA of length $$n$$ whose shortest word has length exactly $$m$$ (exercise).