Check if a NFA accepts a string of non-prime length

Question

Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.

My obvious [edit: wrong] answer is that, if $A$ has $n$ states, then I can simply check if it accepts any word of composite length $\le n$. This violently works, since the input alphabet is defined as finite.

Is there a more refined solution? And would that entail some involved graph search?

P.S. To give some context, this comes from an exercise that previously asked to find algorithms that solved the emptiness problem for regular languages, and the problem of equivalence between two NFAs. I solved those in an analogously simple fashion.

Answer 1

The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.

We can check whether the language accepted by an NFA is infinite as follows:

• Remove all states which are unreachable form an initial state, or from which a final state cannot be reached.
• Check whether the remaining graph contains a cycle.

If the language is infinite, you can immediately answer "Yes". Otherwise, the NFA only accepts words of length at most $n-1$ (where $n$ is the number of states), and you can use the algorithm that you suggest. Your algorithm can be slightly optimized by identifying all letters in the alphabet.