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

Answer 5

The correct option is D.

Here is a step-by-step analysis of each statement:

 

I. $L_1$ is context free but not regular

 

This statement is FALSE.

• $L_1 = \{a^p \mid p \text{ is a prime number}\}$ is not regular, which is true. The gaps between prime numbers are not regular, so it fails the pumping lemma for regular languages.

• However, $L_1$ is also not context-free. It is a well-known example of a language that fails the pumping lemma for context-free languages.

 

II. $L_2$ is not context free

 

This statement is FALSE.

• $L_2 = \{a^n b^m c^{2m} \mid n \ge 0, m \ge 0\}$ is a context-free language (and even a deterministic one).

• A pushdown automaton (PDA) can be built to recognize it:

  1. Read and ignore all the a's.

  2. For every b it reads, push two symbols (e.g., 'X') onto the stack.

  3. For every c it reads, pop one 'X' from the stack.

  4. If the input ends and the stack is empty, accept.

 

III. $L_3$ is not context free but recursive

 

This statement is TRUE.

• $L_3 = \{a^n b^n c^{2n} \mid n \ge 0\}$ is not context-free. A single-stack PDA cannot simultaneously verify two separate dependencies. It cannot check that the number of a's equals the number of b's and that the number of c's is twice the number of b's.

• However, the language is recursive (decidable). A Turing machine can easily be programmed to scan the tape, count the a's, b's, and c's, and then check if the counts satisfy the $n=n$ and $2n$ relationships. This algorithm is guaranteed to halt.

 

IV. $L_4$ is deterministic context free

 

This statement is TRUE.

• $L_4 = \{a^n b^n \mid n \ge 1\}$ is a classic deterministic context-free language.

• A deterministic PDA can be built to:

  1. Read the first a, push a 'Z' (bottom marker) and an 'X', and move to a new state. This ensures $n \ge 1$.

  2. For every subsequent a, push an 'X'.

  3. When a b is read, pop an 'X'.

  4. For every subsequent b, pop an 'X'.

  5. If the input ends and the stack contains only 'Z', accept.

Since only statements III and IV are correct, the answer is D.

Comments

@Subh23   CAN YOU REpLY PLEASE 

---

no you cant do it using 1 stack , read again

---

@Subh23 to add up to my confusion chatgpt kept giving me the same answer , can u verify now 

Answer 6

• Answer: D. III and IV only

• $L_1 = \{a^p \mid p \text{ is prime}\}$:

  • Not regular.

  • Every unary context-free language must be regular.

  • Since $L_1$ is not regular, it is neither regular nor context-free.

• $L_2 = \{a^n b^m c^{2m} \mid n \ge 0, m \ge 0\}$:

  • Can be recognized by a PDA (skip $a$'s, push for $b$'s, pop for $c$'s).

  • Therefore, it is context-free (Statement II is False).

• $L_3 = \{a^n b^n c^{2n} \mid n \ge 0\}$:

  • Requires matching three counts simultaneously, which a single stack cannot do (not context-free).

  • A standard Turing Machine can decide it and always halt.

  • Therefore, it is not context-free but recursive (Statement III is True).

• $L_4 = \{a^n b^n \mid n \ge 1\}$:

  • Deterministic PDA pushes $a$'s and pops on $b$'s without guessing.

  • Therefore, it is deterministic context-free (Statement IV is True).