4
$\begingroup$

A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language.

The answer is "false". I've read this question, but I'm still wondering why $M$ does not necessarily accept an infinite language. Isn't the language $b^*$ infinite? Don't all self-loops look like $b^*$?

$\endgroup$
  • $\begingroup$ If your definition of DFA demands the graph to be complete (i.e. the transition function to be total), every minimal DFA will contain self-loops. $\endgroup$ – Raphael Jan 17 '13 at 13:39
  • $\begingroup$ @Raphael If a self-loop is a transition from a state to itself, then consider the minimal DFA accepting $\mathcal{L} = \{ a^{2n} \}$. This DFA contains two states and no self-loops. $\endgroup$ – Pål GD Jan 17 '13 at 15:28
  • $\begingroup$ @PålGD Oh, right; my argument only seems to work for languages that don't contain a word for every possible prefix. $\endgroup$ – Raphael Jan 17 '13 at 16:52
10
$\begingroup$

the answer is False:

consider a DFA that has no accepting states at all: any loop is not relevant, the language will always be the empty set.

Another option - a loop on a dead state, etc.

However, if it contains a loop on an "accepting path", then indeed the language must be infinite. (this is actually the key idea behind the pumping lemma..)

$\endgroup$
  • $\begingroup$ To generalize, any state that either isn't reachable from the start state, or that cannot reach any accept state can be have self-loops without any immediate consequence. A very easy exercise: Consider the alphabet $\Sigma = \{a\}$ and construct a DFA that accepts the language $\mathcal{L} = \{a\}$. $\endgroup$ – Pål GD Jan 17 '13 at 10:53

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.