Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that the following language $L$ = {$a^n$ where $n$ is a prime number bounded by some fixed $f$} is a regular language because it is finite. Because it's a regular language, I should be able to draw a NFA for it, but I'm stuck as to how. If the value of $f$ was given, I could maybe do it, but I don't know how to represent the value when it is not explicitly given.

Any help would be appreciated. Thanks!

share|cite|improve this question
There will be a slightly different NFA for different values of $f$. I doubt there is a good way to represent the general solution. The automaton is very simple though. If you don't see it, try drawing for several different $f$. You may find a way to write a general solution too. – Karolis Juodelė Aug 12 '12 at 17:53
Thanks for your answer. What do you mean the automaton is very simple? Are you saying drawing one specific one for a value of a specific $f$ is simple? – pauliwago Aug 12 '12 at 17:58
There is only one symbol. You only need a single chain of states starting at $q_0$, ending at $q_f$ and accepting at $q_p$ for a prime $p$. I don't see how non-determinism could be beneficial here. – Karolis Juodelė Aug 12 '12 at 18:02
How can I do this? Aren't prime numbers arbitrarily "spaced"? I can do it for the first 100 for example, manually counting each scenario, but this isn't wha I'm looking for... – pauliwago Aug 12 '12 at 19:28
@pauliwago: The "isn't what I'm looking for" kind of solution is the best you can get. – Henning Makholm Aug 12 '12 at 20:49
up vote 2 down vote accepted

Note that you do not want to construct a single automaton, but rather yuo want to describe a method that, given $f$, can describe an automaton (which may differ for each $f$). The straightforward method described by Karolis Juodelè (have one state for each number $0,\ldots,f$ and make those with prime indices accepting) does this.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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