MadeEasy Test Series: Theory Of Computation - Finite Automata

Question

Let L = {(aP)*⎪P is a prime number} and Σ={a}. The minimum number of states in NFA that accepts the language L are ________.

i don't think it is even a regular language. then how can NFA be generated?

Comments

Duplicates:

https://gateoverflow.in/37096/madeeasy-test-series-theory-of-computation-finite-automata

https://gateoverflow.in/253509/can-a-p-where-p-is-a-prime-number-be-an-nfa

https://gateoverflow.in/141722/minimum-number-of-state

---

Duplicates:

https://gateoverflow.in/37096/madeeasy-test-series-theory-of-computation-finite-automata

https://gateoverflow.in/253509/can-a-p-where-p-is-a-prime-number-be-an-nfa

https://gateoverflow.in/260025/madeeasy-test-series-theory-of-computation-finite-automata

---

https://gateoverflow.in/141722/minimum-number-of-state

https://gateoverflow.in/253509/can-a-p-where-p-is-a-prime-number-be-an-nfa

https://gateoverflow.in/260025/madeeasy-test-series-theory-of-computation-finite-automata

Answer 1

Ans is 3 states

Answer 2

Minimum 3 states-

(${a^p}$)* = {ϵ, (a²)*, (a³)*,....}

={ϵ,a²,a³,a⁴,${a^5}$,.....}

 

Comments

How you are accepting a^4, a^6 ......

Moreover its a CSL, how come we can implement NFA on it?

---

(a²)* generates all even lenght strings ..esilon,aa,aaaa,aaaaaa,......

In one of my comment (above)--

{2,3,2+2,5,2+2+2,7,2+2+2+2,3+3+3,....}  for >=2a's [this is how all strings generated whose length >=2].

Is it clear?

---

Thank you. Got it!

Interesting question... :)

Answer 3

L = { epsilon , (a^(2))* , (a^(3))* , .(a^(5))*.........}^(*)

3 states would be sufficient for this

Comments

@Kaluti

it should be L = { epsilon , (a^(2))* , (a^(3))* , .(a^(5))*.........}*

* should be present outside '{ }'

---

ya u are right

Answer 4

It will be 3. Think of it as a^n where  n=0 or n>=2.