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 (103k points)
edited by | 1.4k 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 (358k 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
+5 votes

so the option c is correct.

answered by Active (2.1k 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 (8.5k points)

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

40,855 questions
47,521 answers
62,279 users