Computer Sciences > GATE 2026 SET-2 > Theory of Computation
Let Σ = {a, b, c, d} and let L = {aⁱ bʲ cᵏ dˡ | i, j, k, ℓ ≥ 0}. Which of the following constraints ensure(s) that the language L is context-free?
A
i + k = j + ℓ
B
i = k and j = ℓ
C
i = ℓ and j = k
D
i + j = k + ℓ

Correct : a,c,d

The correct answers are Options A, C, and D
Option A — i + k = j + ℓ: This is a linear balance constraint. A PDA can handle it by pushing for every ''''a'''' read, popping for every ''''b'''', pushing for every ''''c'''', and popping for every ''''d''''. The stack is empty at the end iff i − j + k − ℓ = 0, i.e., i + k = j + ℓ. CFL ✓ Correct.
Option B — i = k and j = ℓ: This gives the language {aⁱ bʲ cⁱ dʲ}, which requires two independent cross-serial counts to be matched simultaneously. A single-stack PDA cannot compare both i with k and j with ℓ independently when they interleave. This is a context-sensitive language. Not CFL ✗ Incorrect.
Option C — i = ℓ and j = k: This gives the language {aⁱ bʲ cʲ dⁱ}, which has a perfectly nested structure. A PDA pushes i a''''s, then pushes j b''''s, then pops j for c''''s (matching j = k), then pops i for d''''s (matching i = ℓ). A simple grammar S → aSd | T, T → bTc | ε generates exactly this language. CFL ✓ Correct.
Option D — i + j = k + ℓ: Another linear balance constraint. A PDA pushes for every ''''a'''' and ''''b'''', and pops for every ''''c'''' and ''''d''''. The stack is empty iff i + j = k + ℓ. CFL ✓ Correct.

Similar Questions

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s,p,q,r}, with s being th...
#952 MCQ
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: Which one of the fo...
#956 MCQ
Consider the context-free grammar G below: S -> aSb | X X -> aX | Xb | a | b where S and X are non-terminals, and a and b are terminal symbols. The starting non...
#974 MCQ

Related Topics

GATE CS 2026 Set-2 Q48 context-free language GATE 2026 CFL constraints GATE CS PDA pushdown automaton GATE 2026 theory of computation GATE CS 2026 aibj ck dl context free GATE cross-serial dependency GATE CS CFL pumping lemma GATE 2026

Unique Visitor Count

Total Unique Visitors

Loading......