1.7k views

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.
edited | 1.7k views

(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
+23

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

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
+4

DFA for C) 0
How D CSL ?
+1
as it cannot be implemented by Pda
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 .
0
Could u explain how this would be accpeted in LBA ?
+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.
+2
@arjun how did u get    a∗b(a∗ba∗ba∗b)+a∗  as regular expression?
0
@arjun sir if we talk more specific then i think option A is DCFL
0
Can we write D as L=w^2.... Then it should be regular so the option c is correct.

answered by Active (2.2k points)

(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 ∗ .....ba ∗ such that there are exactly 3k + 1 bs and a ∗ s surrounding each b in the grammar. (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)