Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Raphael Jan 17 '13 at 13:39
    
@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. –  Pål GD Jan 17 '13 at 15:28
    
@PålGD Oh, right; my argument only seems to work for languages that don't contain a word for every possible prefix. –  Raphael Jan 17 '13 at 16:52

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
Thank you! That explains! –  goldfrapp04 Jan 17 '13 at 8:11
    
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\}$. –  Pål GD Jan 17 '13 at 10:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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