2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Without further restrictions, I agree with you $\endgroup$ – siracusa Sep 30 '19 at 6:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 30 '19 at 7:28
  • $\begingroup$ At least one of the three statements will be true. But note that (b) and (c) can both be true at the same time. $\endgroup$ – gandalf61 Sep 30 '19 at 11:06
  • 2
    $\begingroup$ 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. $\endgroup$ – gandalf61 Sep 30 '19 at 11:13
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Sep 30 '19 at 15:22
2
$\begingroup$

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).

| cite | 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.