0 votes 0 votes $L=\left \{ a^{n}:\text{n is the product of two prime number} \right \}$$L$ is regular or non regular? Theory of Computation theory-of-computation regular-language + – saumya mishra asked Aug 3, 2018 edited Aug 3, 2018 by srestha saumya mishra 508 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply srestha commented Aug 3, 2018 reply Follow Share I think using pumping lemma we can say it is non regular 0 votes 0 votes saumya mishra commented Aug 3, 2018 reply Follow Share How to apply pumping lemma for this given language?? 0 votes 0 votes goxul commented Aug 3, 2018 reply Follow Share https://www.seas.upenn.edu/~cit596/notes/dave/pumping6.html 1 votes 1 votes daksirp commented Aug 4, 2018 i edited by daksirp Aug 4, 2018 reply Follow Share you can understand this way, since it is infinite language 'n' should be in AP(Arithmetic progression), (ex : in place of 'n', if it were 2p+1 or 5p or 9p+100 where p is any natural number....etc then it would have been in AP) then only loop can be formed, thats what pumpimg lemma says, => if a loop cant be formed in an infinite language, then it is not regular. in the above language, n is product of two prime numbers, so we cant form a loop. 0 votes 0 votes Shaik Masthan commented Aug 4, 2018 reply Follow Share @ daksirp, did you mean L={a2n+1 : n is a prime number} is REGULAR? 0 votes 0 votes daksirp commented Aug 4, 2018 reply Follow Share no, language should be in AP. not n. ex : (a, aaa, aaaaa, ......), { a2n+1 | n >= 0 }, this forms an AP. in ur que, n is a prime number so it isnt in AP. therefore we cannot form a loop, so not regular.. 0 votes 0 votes Shaik Masthan commented Aug 4, 2018 reply Follow Share I commented, before you edited your own comment 0 votes 0 votes daksirp commented Aug 4, 2018 reply Follow Share yaaaa. 0 votes 0 votes Please log in or register to add a comment.