World's most popular travel blog for travel bloggers.

Do self-loops in DFA cause infinite languages?

, , No Comments
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

0 comments:

Post a Comment

Let us know your responses and feedback