The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
56 views
$L=\left \{ a^{n}:\text{n is the product of two prime number} \right \}$$L$ is regular or non regular?
asked in Theory of Computation by Active (1.2k points)
edited by | 56 views
0
I think using pumping lemma we can say it is non regular
0
How to apply pumping lemma for this given language??
0
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

daksirp, did you mean

L={a2n+1 : n is a prime number} is REGULAR?

0

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
I commented, before you edited your own comment
0
yaaaa.

Please log in or register to answer this question.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,203 questions
45,703 answers
132,818 comments
49,750 users