# building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

$$\{a^p; p$$ is a prime number, $$m$$ is a fixed number and $$m\geq p \geq 0 \}$$

I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $$m$$ is. Is there a way to draw the NFA regardless?

• You either know what $m$ is, and then you can build the DFA, or you don't, and then you don't know what language you are talking about.
– user114966
Aug 8 '20 at 2:27
• @Dmitry I think the question is: what is an algorithm which takes $m$ as an input and outputs a description of an NFA that accepts the language stated in the question. Aug 8 '20 at 4:40

Your DFA has states $$S_0$$ to $$S_m$$ and E. You start at state $$S_0$$.
Any state transitions to E if the next input symbol is not a. States $$S_m$$ and E transition to state E on any input; state $$S_i$$ for 0 ≤ i < m goes to state $$S_{i+1}$$ on input a.
$$S_i$$ is an accepting state if and only if i is a prime. All other states are non-accepting.