Problem Detail: 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^*$?
Asked By : goldfrapp04
Answered By : Ran G.
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..)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/8982
