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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,855 questions

47,521 answers

145,897 comments

62,279 users