0 votes 0 votes 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? Theory of Computation made-easy-test-series theory-of-computation finite-automata + – khushtak asked Jan 21, 2016 edited Mar 5, 2019 by akash.dinkar12 khushtak 2.1k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Shiva Sagar Rao commented Apr 24, 2021 reply Follow Share 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 0 votes 0 votes Shiva Sagar Rao commented Apr 24, 2021 reply Follow Share 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 0 votes 0 votes Shiva Sagar Rao commented Apr 24, 2021 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes Ans is 3 states resuscitate answered Jan 21, 2016 selected Jan 21, 2016 by Pooja Palod resuscitate comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Minimum 3 states- (${a^p}$)* = {ϵ, (a²)*, (a³)*,....} ={ϵ,a²,a³,a⁴,${a^5}$,.....} Verma Ashish answered Nov 1, 2018 edited Nov 1, 2018 by Verma Ashish Verma Ashish comment Share Follow See all 3 Comments See all 3 3 Comments reply Shamim Ahmed commented Nov 1, 2018 reply Follow Share How you are accepting a^4, a^6 ...... Moreover its a CSL, how come we can implement NFA on it? 0 votes 0 votes Verma Ashish commented Nov 1, 2018 reply Follow Share (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? 0 votes 0 votes Shamim Ahmed commented Nov 1, 2018 reply Follow Share Thank you. Got it! Interesting question... :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes L = { epsilon , (a^(2))* , (a^(3))* , .(a^(5))*.........}^(*) 3 states would be sufficient for this Kaluti answered Aug 12, 2017 edited Aug 12, 2017 by Kaluti Kaluti comment Share Follow See all 2 Comments See all 2 2 Comments reply joshi_nitish commented Aug 12, 2017 reply Follow Share @Kaluti it should be L = { epsilon , (a^(2))* , (a^(3))* , .(a^(5))*.........}* * should be present outside '{ }' 0 votes 0 votes Kaluti commented Aug 12, 2017 reply Follow Share ya u are right 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It will be 3. Think of it as a^n where n=0 or n>=2. ad140 answered Nov 1, 2018 ad140 comment Share Follow See all 0 reply Please log in or register to add a comment.