2
$\begingroup$

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!

  • 0
    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.2012-08-12
  • 0
    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?2012-08-12
  • 1
    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.2012-08-12
  • 0
    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...2012-08-12
  • 2
    @pauliwago: The "isn't what I'm looking for" kind of solution is the best you can get.2012-08-12
  • 0
    I understand. Thanks2012-08-12

1 Answers 1

2

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.