Let Sigma = {a, b, c, d} and let L = {a^i b^j c^k d^l | i, j, k, l = 0}. Which of the following con

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2026 GATE-CS Theory of Computation paper.

Q: How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2026 question covers Regular and Context-Free Languages topic.

Q: What is the difficulty level of this question?

This GATE-CS 2026 Theory of Computation question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Let Sigma = {a, b, c, d} and let L = {a^i b^j c^k d^l | i, j, k, l >= 0}. Which of the following constraints ensure(s) that the language L is context-free?

Accepted Answer

Correct Answer: (A), (C), (D)Concept -- Context-Free Languages: A language is context-free if it can be recognized by a PDA (one stack).• A: i + k = j + l. This is equivalent to i - j = l - k. A PDA can push for a and c, pop for b and d, or use two phases. CFL.• B: i = k and j = l. This requires comparing i with k and j with l simultaneously, which is essentially {a^i b^j c^i d^j}. This is not context-free (it’s the intersection of two CFLs? Actually it’s known to be non-CFL because it requires two independent comparisons, which a PDA cannot do with one stack. It is a deterministic context-sensitive language.• C: i = l and j = k → a^i b^j c^j d^i. This is context-free (push a, then push b, then pop b with c, then pop a with d). CFL.• D: i + j = k + l. This is total count equality, can be done with a single stack (push for a,b; pop for c,d). CFL.Why B is incorrect: It requires two independent counters, beyond the power of a PDA.Note: The pumping lemma for CFL can be used to show that {a^i b^j c^i d^j} is not CFL. The others are variations of well-known CFLs like {a^n b^n} or {a^n b^n c^m d^m}.

Let Sigma = {a, b, c, d} and let L = {a^i b^j c^k d^l | i, j, k, l >= 0}. Which of the following constraints ensure(s) that the language L is context-free?

Master GATE-CS with Our Test Series

More Questions from Regular and Context-Free Languages

Frequently Asked Questions

Let Sigma = {a, b, c, d} and let L = {a^i b^j c^k d^l | i, j, k, l >= 0}. Which of the following constraints ensure(s) that the language L is context-free?

Master GATE-CS with Our Test Series

More Questions from Regular and Context-Free Languages

Frequently Asked Questions