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^*$?

  • $\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, 2013 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, 2013 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, 2013 at 16:52

1 Answer 1


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

  • $\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, 2013 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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