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
    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.