658 views

2 Answers

Best answer
3 votes
3 votes

ap will give = a2, a3, a5, a7, a11, a13 ....

and

(ap)* = (a2)*, (a3)*, (a5)*, (a7)*, (a11)* ...

which is equals to Ɛ, a2, a4, a6, a8, ..... a3, a6, a9, a12........ a5, a10, a15........ a7, a14, a21......

from sieve of Eratosthenes (prime no algorithm) it will cover all string except length 1.

i,e. Ɛ, a2, a3, a4, a5, a6, a7, a8 .....

So No of states in NFA = 3

selected by
2 votes
2 votes

a where p is a prime ---- is not a regular language without a bound in p

2 is a prime so 

(a2)* --- it derives all aa, aaaa, aaaaaa ....

(a3)* --- it derives all aaa, aaaaaa, aaaaaaaaa...

so on for all primes

 it completes the set of all strings of a except a 

so it should accept strings of min length of 2 --- so number of states will be 3 (without a dead state)--asked for minimum so answer is 3

Related questions

1 votes
1 votes
3 answers
1
0 votes
0 votes
1 answer
2
jam asked Oct 17, 2023
210 views