GATE CSE 2017 Set 2 | Question: 40

Question

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

• A. I, II and IV only
• B. II and III only
• C. I and IV only
• D. III and IV only

Comments

Explain L2 and L3 please

---

can anyone pls tell me why l3 is not cfl

---

Shreyash31 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.

Answer 1

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

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

So, option is D.

Comments

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

---

See this:

https://gateoverflow.in/104949/l-ap%C2%A0∣-p%C2%A0is-a-prime%C2%A0

---

Thanks @smsubham

I got another reference for this.

Link: https://www.cs.auckland.ac.nz/~nies/Students/Bax380project2010.pdf

---

$L_1 = \{a^p \mid p \text{ is a prime number} \} \ is \ CSL$

$L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \} \ is \ DCFL$

$L_3 = \{a^n b^n c^{2n} \mid n \geq 0 \} \ is \ CSL$

$L_4 = \{ a^n b^n \mid n \geq 1\} \ is \ DCFL$

Answer 2

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.

Comments

@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

Answer 3

option d is correct

Answer 4

answer is D