L = { w | such that n_{b}(w) mod 3=1 }

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

Which one of the following is **TRUE**?

- The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular.
- The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular.
- The language $L$= $\left\{ w \mid w \text{ has } 3k+1 \text{ } b's \text{ for some } k\in N \text{ with } \Sigma=\left\{ a,b \right\}\right\}$ is regular.
- The language $L = \left\{ww \mid w \in \Sigma^* \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.

+22 votes

Best answer

0

@Arjun Sir b,c cannot be CFL since the powers are not in AP fine.but hw can i say a language is csl plz xplain

0

@Praveen_Saini SIR , Could u explain it a bit more ?

Supose if it were L = {wxw} When I first see w I push it to stack when i see x skip and pop remeaining w from stack . This could be accepted by pda .

But, L={ww} We do not know when to pop w from the stack, Is this the reason for $ww$ not being accepted by PDA .

Could u explain how this would be accpeted in LBA ?

+1

w is not just w , w is a string over {0,1} , such as 011, so after pushing 011 in stack , you get 0 from second w but at that time 1 is at top of stack .

+4

Not necessary - any language that is decidable and does not require non-linear space complexity is CSL.

0

@ Arjun SIR , I also read that . But How to find it with a given language that part im not able to follow . ie With a given laguage how to find it take non-linear space and it is decidable

+4

Decidability you should know. But see as long as you can write a C code for a problem - that is decidable. And also, no GATE question ever had a language which is recursive but not CSL. You can google and get an example for that - all of the languages being discussed here are either not recursive or CSL.

+3 votes

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,720 questions

52,823 answers

183,476 comments

68,570 users