The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

Which one of the following is TRUE?

  1. The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular.
  2. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular.
  3. 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.
  4. The language $L = \left\{ww \mid w \in \Sigma^*    \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.
asked in Theory of Computation by Veteran (115k points)
edited by | 1.7k views

3 Answers

+22 votes
Best answer

(A) is CFL and (B) and (D) are CSL.

(C) is regular and regular expression for (C) would be: $$a^*b(a^*ba^*ba^*b)^+a^*$$

answered by Veteran (386k points)
edited by

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

@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

DFA for C)

How D CSL ?
as it cannot be implemented by Pda

@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 ? 

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 .
Could u explain how this would be accpeted in LBA ?
Not necessary - any language that is decidable and does not require non-linear space complexity is CSL.

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 

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.
@arjun how did u get    a∗b(a∗ba∗ba∗b)+a∗  as regular expression?
@arjun sir if we talk more specific then i think option A is DCFL
Can we write D as L=w^2.... Then it should be regular
+5 votes

so the option c is correct.

answered by Active (2.2k points)
+3 votes

(A) L = {a n b n |n >= 0} is not regular because there does not exists a finite automaton that can derive this grammar. Intuitively, finite automaton has finite memory, hence it can’t track number of as. It is a standard CFL though. (B) L = {a n b n |n is prime} is again not regular because there is no way to remember/check if current n is prime or not. Hence, no finite automaton exists to derive this grammar, thus it is not regular. (C) L = {w|w has 3k+1 bs} is a regular language because k is a fixed constant and we can easily emulate L as a ∗ ba ∗ ∗ such that there are exactly 3k + 1 bs and a ∗ s surrounding each b in the grammar.v_24(D) L = {ww| w ∈ Σ ∗ } is again not a regular grammar, infact it is not even a CFG. There is no way to remember and derive double word using finite automaton. Hence, correct answer would be (C). 

answered by Loyal (9.3k points)

Related questions

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
48,720 questions
52,823 answers
68,570 users