0 votes
0 votes

$\\ L1=(w | n_{a}(w)=n_{b}(w))\\ L2=(a^nb^ la^k | k\geqslant n+l)\\ L3=(a^nb^ la^k | k\neq n+l)\\ L4=(a^nb^ la^k | n=l \ or \ l\neq k)\\ L5=(a^nb^l |n\leqslant l)\\ L6=(w | n_{a}(w)\neq n_{b}(w))\\ L7=(ww | w \ \epsilon (a,b)^* )\\ L8=(wwww^R | w \ \epsilon (a,b)^*)\\ L9=(a^n | n\geqslant 2, is \ a \ prime \ number)\\ L10=(a^n | n \ is \ not\ a\ prime\ number )\\ L11=(a^n | n=k^3 for\ some\ k\geqslant 0)\\ L12=(a^n| n= 2^k for\ some\ k\geqslant 0)\\ L13=(a^n| n \ is\ a\ product\ of\ two\ numbers)\\ L14=(a^n|n\ is\ either\ prime\ or\ the\ product\ of\ two\ or\ more\ prime\ numbers )\\ L15=(L^*|L\ is\ the\ language\ in\ part\ L9 )$

These languages are given in order to prove whether they are regular or not by making use of pumping lemma.I am interested in finding that If the language is regular then it’s okay but if the language is not regular then what are they?

Mt attempt:

dcfl, dcfl, dcfl, ncfl, dcfl, dcfl, csl, csl, csl, csl, csl, csl, csl, csl, regular ??

in Theory of Computation


Regular expression for $L13= a^+\;$ ,if n>0

So it is regular

Sorry,  L13 is product of two prime numbers. and I think now it will not be regular but then what it will be, is it csl which i have written?

But L14 is regular for sure !!

And please verify for others, if something’s wrong do tell.

Yes then it will be csl

It is not L14, it is L15 which is regular ;)

All are correct..

No, L14 is also regular.

Reason for that: Every non prime number can be represented with the help of two or more prime numbers.Now, we start to think all non prime numbers are represented but what about prime.How can we represent them? No need for that because they are already given in the question.

$\therefore$ All strings can be generated and making this language as regular.

Yes you are right..

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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.