1
$\begingroup$

So I've seen this claim being made on different questions:

Do self-loops in DFA cause infinite languages?

I'd like to find formal proof for this.

I think I should also note that an "accepting path containing a cycle" is probably defined as a path in a graph so that the states in the DFA are nodes in the graph and there must be a cycle and at least one accepting state in that path.

$\endgroup$
  • $\begingroup$ An accepting path is a path from the initial state to an accepting state. Perhaps this will help you prove the claim. $\endgroup$ – Yuval Filmus Mar 26 at 19:05
  • $\begingroup$ what exactly are you asking? whether the statement 'All DFA's containing cycles define an infinite language' is true or not? $\endgroup$ – lox Mar 26 at 19:22
1
$\begingroup$

If the DFA contains a path from the start node to an accepting state that contains a cycle, then the DFA is an infinite language. The proof is easy: you can go around the cycle as many times as you like. Depending on how many times you go around the cycle, you get a different word accepted by the DFA; the more times around the cycle, the longer the word (so it has to be different from any word where you went around the cycle a different number of times). There are infinitely many possibilities for how many times you can choose to go around the cycle, so infinitely many words accepted by the DFA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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