0
$\begingroup$

$\{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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user114966
    Aug 8 '20 at 2:27
  • $\begingroup$ @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. $\endgroup$ Aug 8 '20 at 4:40
0
$\begingroup$

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.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .