# Proof that whether a regular language is finite is decidable [duplicate]

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When you generate all strings from length 0 to n, if the machine accepts any of them then the language is non-empty. We don't have to check words with length > n because of the pumping lemma. The question claims that you can solve the decision problem for finiteness in a similar way.

I know intuitively that a regular language is finite if its finite, well-formed regular expression does not contain a Kleene star, but I don't know how to convert this notion around. My thought is that we have to know if there are any words in the language whose length is greather than n, but that requires checking all words.

Then I thought: Have the machine count the number of states n in the FSM. Generate all of the strings of length 0 to n. Then, check every word to see if the only possible way to pump this word xyz is to make y≡λ. If every word pumps only according to this condition, then the language is finite. However, this feels somehow incomplete.

Could someone give me a hint or push me in the right direction? Thanks.

## marked as duplicate by xskxzr, David Richerby, Evil, Apass.Jack, Discrete lizard♦Mar 28 at 18:44

• If you have a decider on regular expressions, what's the big deal? Convert the automaton to regular expressions (that's certainly computable) -- reduction obtained. – Raphael Apr 7 '16 at 7:45
• Alternatively, look at the proof of the Pumping lemma and see where the pumping comes from. That gives you one direction of the proof. – Raphael Apr 7 '16 at 7:46

If $L$ is infinite, it contains strings of unbounded length. Think about the sequence of states visited by the automaton when these strings are accepted. This will give you a condition of the form "$M$ accepts an infinite language implies $X$". Now check that it's actually "if and only if $X$."
How about checking all the strings of length $n$ to 2$n$? Would that be helpful to derive the required conclusion?