6,496 views

Consider the following languages.

• $L_1 = \{a^p \mid p \text{ is a prime number} \}$
• $L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \}$
• $L_3 = \{a^n b^n c^{2n} \mid n \geq 0 \}$
• $L_4 = \{ a^n b^n \mid n \geq 1\}$

Which of the following are CORRECT?

1. $L_1$ is context free but not regular
2. $L_2$ is not context free
3. $L_3$ is not context free but recursive
4. $L_4$ is deterministic context free
1. I, II and IV only
2. II and III only
3. I and IV only
4. III and IV only

can anyone pls tell me why l3 is not cfl

Make a PDA for that language or try to write grammar. The problem is after verifying #a=#b, the same number has to be ½ of #c, which cannot be verified as the stack will be empty.

### Subscribe to GO Classes for GATE CSE 2022

$L_1$ is Csl, $L_2$ is context free

$L_3$ is not Context free and $L_4$ is Dcfl

So, option is D.

by
5 14 22

Please explain how L1 is a CSL?
I'm not able to imagine how L1 could be accepted by LBA which has limited tape.

Thanks @smsubham

I got another reference for this.

L1 : {aa,aaa,aaaaa,aaaaaa,......}.It is CSL because prime numbers does not have a fixed pattern.

L2 : push a push b then pop one b for each 2 c's and accept it when top of stack has a.It is DCFL.

L3: for a and b then for b and c two comparisons and therefore two stacks are required .It is CSL.

L4 : Classical example of DCFL. Push a then pop a for each b.

Options

I. wrong because L1 is not CFL.

II. wrong because L2 is DCFL so it is CFL .

III. Right because every CSL is Recursive but not CFL.

IV. Right it is DCFL.

Since III and IV are only correct options Ans is D.

by
9 33 67

### @Ravi_1511 Brother, in L2 = can I push 2 "b's" for one b and pop single "b" for every "c"

" II. wrong because L2 is DCFL so it is CFL "

This statement makes it a much accurate answer than the best answer

@Ravi_1511 @Arjun Sir, @Bikram Sir  , Pls check my understanding:

For L3, we needed two comparisons back-to-back on the same variable(n).

Thats why it is not CFL.

But, If we see 1 in this problem ,

https://gateoverflow.in/204109/gate2018-35

We needed 2 comparisons too, but on different variables.

Thats why that problem was CFL, & this problem is not CFL

option d is correct
by
1 1 1

by
1 2 7