self doubt

Question

Let L =  { (a^p)* | p is prime number } and input is {a} . what is minimum number of state in NFA and DFA ?

Comments

$L=\{\varepsilon ,aa,aaa,aaaa,aaaaa,\ldots\}$

Minimum finite automata has 3 states

---

Verma Ashish 1 is also prime na....

---

no

Answer 1

3 state are required

Answer 2

this language accept all string except 'a'.

i.e. ((a)^p)* = {(a^2)*, (a^3)*, (a^5)*...... so on}

which is  equal to { (aa)*, (aaa)*, (aaaaa)* ..........}

hence, create directly a dfa which accept all stings except 'a' OR create a dfa of only accepting 'a' and then take complement of it.

hence needs 3 state.

Comments

Here , we can construct NFA with 2 states and DFA with 3 states.

in NFA , ( Q0, a)  ---> (Q0) or (Q0, a) ----> Q1

            (Q1,a)  ----> Q0

Here Q0 is final state. In this way NFA is possible with two state.  Because in NFA among all the transition, one transition lead to final state. Here is possible. 

Am i wrong ?

---

If q0 is the final state then it is going to accept epsilon as well.

---

Yes, language generate the epsilon. see it in question

---

Sorry I wrote about epsilon by mistake. Single a would be accepted by the nfa through (q0,a)->(q0) move.