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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 1 at 9:34

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.

| cite | improve this answer | |
  • $\begingroup$ Thank you! I didn't see the pumping lemma under that light. When you say "identifying all letters" you simply mean that the algorithm should stop reading a specific input string when the NFA returns the empty set of states? $\endgroup$ – Davide Sep 1 at 10:52
  • $\begingroup$ I mean that the algorithm can treat all letters as the same letter. $\endgroup$ – Yuval Filmus Sep 1 at 11:02
  • $\begingroup$ Oh right, in the end we only care about the length of strings. Thanks! $\endgroup$ – Davide Sep 1 at 11:06

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.