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

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.

• Your answer doesn't work. Consider an NFA with a single accepting state and a self-loop. It doesn't accept any word of composite length $\leq 1$, but it does accept words of composite length. In contrast, if the single state wasn't accepting, it would not accept any word of composite length. Sep 1, 2020 at 9:34

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.