patternModerate
Do self-loops in DFA cause infinite languages?
Viewed 0 times
dfainfinitelanguagesloopscauseself
Problem
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^$?
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^$?
Solution
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..)
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..)
Context
StackExchange Computer Science Q#8982, answer score: 11
Revisions (0)
No revisions yet.