Context-Free Language Questions in GATE CSE: Method and Traps

Context-free questions in GATE CSE arrive in three shapes: place four given languages in the Chomsky hierarchy, decide which closure or decidability statements are true, or read off the language of a grammar or a pushdown automaton. All three come from the same small set of facts. Marks are lost here to half-remembered rules rather than to difficulty, and since 2021 these questions are usually multiple-select, where half-knowledge scores zero.

Key takeaways

• One stack means one comparison, and the stack returns symbols in reverse order.
• One linear relation between symbol counts in nested order is context free. Two independent relations are not.
• ww reversed is context free; ww and a^n b^n c^n are not.
• DCFLs are closed under complement. CFLs are closed under neither complement nor intersection.
• For context-free grammars, membership, emptiness and finiteness are decidable; ambiguity, universality, equivalence and regularity are not.
• For Turing machines, any non-trivial property of the accepted language is undecidable; syntactic and step-bounded properties are decidable.

Where these questions sit in the paper

Third-party analyst compilations place Theory of Computation at 9, 7, 9, 6, 8, 5.3, 5, 10, 9, 8, 8, 9, 9, 7, 9, 7, 9 and 7 marks across the papers from 2009 to 2026. The average is about 7.8, the minimum 5 and the maximum 10; the 2009 to 2017 average is 7.6 and the 2018 to 2026 average is 8.1. The direction is flat. These figures are unofficial, and sources disagree by two or three marks because borderline questions get classified under Compiler Design or Discrete Mathematics instead. Check the current notification for the paper structure.

Analysts rate Theory of Computation, alongside Algorithms, as one of the most consistently difficult subjects, because almost nothing here is a formula substitution. The full subject ranking sits in the Theory of Computation important topics guide. The official 2027 syllabus names push-down automata, context-free languages, the pumping lemma, Turing machines and undecidability, so none of what follows is optional.

The one-stack test

Do not start with the pumping lemma. Start by counting comparisons.

A finite automaton has no memory beyond its state, so it can only count modulo a fixed number. A pushdown automaton adds one stack, which stores an unbounded count but can be spent exactly once and returns what it stored in reverse.

That gives a three-line test you can run in about thirty seconds on an unfamiliar language.

1. Only bounded counts, residues modulo a fixed number, or a fixed pattern of positions? Regular.
2. Exactly one unbounded comparison, laid out so a stack can serve it in last-in-first-out order? Context free.
3. Two unbounded comparisons at once, or one comparison in the wrong order? Not context free.

Run it on the standard cases. The language a^m b^n c^(m+n) is context free: push an a for each a, push a b for each b, then pop one symbol per c. One stack, one comparison, nested correctly. The language a^n b^m c^n d^m is not, because the a to c match and the b to d match interleave, so the stack would have to return the a block after the b block sitting on top of it. And a^n b^n c^n fails because the stack is empty after the b block, leaving the c block nothing to check against.

Why ww reversed is in and ww is out

This pair is asked so often it is worth understanding rather than memorising.

For a string of the form x followed by the reverse of x, the machine pushes each symbol of the first half. When the second half starts, the symbol it must match is the last one pushed, which is exactly what pops first. Stack discipline and language agree.

For ww the second half arrives in the same order as the first, while the stack hands back the reverse. The machine would need a queue, not a stack. That is also why a two-stack pushdown automaton is as powerful as a Turing machine: two stacks simulate a tape.

One cousin to watch. A language of the form x y x reversed, with y free to be any string, is usually regular, because the free middle absorbs everything and x can shrink to a single symbol. Read set-builder definitions carefully for that free middle; it flips the answer.

Deterministic context-free versus context-free

A deterministic pushdown automaton has at most one move available in every configuration. The class it accepts, DCFL, is a strict subset of CFL, and this is the only classic machine pair where determinism costs power: DFA and NFA are equal, deterministic and non-deterministic Turing machines are equal, DPDA and NPDA are not.

The single fact you need is that DCFLs are closed under complement and CFLs are not. With a deterministic machine you can force every input to drive exactly one run and then swap accepting and non-accepting states. With a non-deterministic machine, one rejecting branch does not mean rejection, so swapping does not work.

Two consequences generate most of the questions. If a language is context free but its complement is not, it cannot be a DCFL. And the union of two DCFLs need not be a DCFL: for the union of a^n b^n and a^n b^(2n), a deterministic machine would have to commit while reading the b block to which count it is checking. That language is context free, not deterministic, and inherently ambiguous.

The closure grid

Learn this as a picture, not as a list. Yes means always closed.

The complement row carries most of the marks. DCFL is the odd column: complement yes, everything else no. The complement of a context-free language is always recursive, so a statement calling it recursive is true while a statement calling it context free is false. Recursively enumerable languages are not closed under complement, and the repair rule is that if a language and its complement are both recursively enumerable, the language is recursive.

The last row is the workhorse for proofs. Intersect an unknown context-free language with a regular one, get a^n b^n c^n, and the unknown language was not context free.

Ambiguity and inherent ambiguity

A grammar is ambiguous if some string has two distinct parse trees, equivalently two distinct leftmost derivations. Counting parse trees for a short string is a standard numerical-answer item; build a recurrence over the split points instead of drawing trees.

A language is inherently ambiguous if every grammar for it is ambiguous, and such languages are never deterministic context free, which makes the property a classification tool rather than vocabulary. Keep the two levels apart: an ambiguous grammar can perfectly well generate a deterministic language, in which case the grammar is the problem and not the language. This is also where the subject feeds straight into parsing, so the same facts pay twice in the Compiler Design important topics guide.

The decidability grid

Same shape, different question. Decidable means an algorithm always halts with the correct yes or no.

Read it as four rules. Everything about finite automata and regular expressions is decidable. For context-free grammars only membership, emptiness and finiteness are decidable, and every semantic question past that point is not, including ambiguity, universality, equivalence, inclusion, regularity of the language and emptiness of an intersection. Deterministic context-free languages sit in between. For Turing machines essentially nothing about the language is decidable.

The undecidability shortcut

When a question hands you a set of the form "all machine encodings whose language has property P", one sentence settles it: any non-trivial property of the language accepted by a Turing machine is undecidable. Non-trivial means some recognisable language has it and some does not.

Check the two escapes before you tick the box.

• Syntactic properties are not properties of the language. Number of states, presence of a transition on a given symbol, size of the tape alphabet: all decidable.
• Step-bounded and length-bounded properties are decidable. Whether the machine runs more than k steps on some input, or reaches a state in exactly k steps, depends only on inputs of length at most k plus one, so you can simulate them all.

For a property that is both non-trivial and semantic, the follow-up is whether it is at least recognisable. The test is whether a yes can be certified by finite computation. Accepting some string of length at most k is recognisable; accepting nothing is not, though its complement is; whether the language is regular is neither.

Practising for the multiple-select format

These statements are now asked as multiple-select questions with no partial credit, so fifty percent recall scores zero rather than half. Drill accordingly.

Write both grids from blank paper twice a week until they come out without hesitation, then stop revising and only test yourself. On every past question, classify each option independently and write one line of justification for each before looking at the key. That line is the part being examined.

Keep a list of the languages that fooled you once, because the shapes repeat even when the letters change: free middles, unions of two deterministic languages, three-way count equalities, copy languages. The cross-subject version of that habit is in common mistakes that cost marks, and the evidence on which forms repeat is in the guide to the most repeated topics in GATE CSE.

Beyond the method here, the Theory of Computation chapter of the GATE CSE 2027 book carries a year-by-year reconstruction of which concepts appeared when, plus a worked bank of classification, closure and decidability items.