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
0 comments:
Post a Comment
Let us know your responses and feedback