GATE Theory of Computation previous year questions

abb via S → aSbS: either the first S → bS → b and the second S → ε (a·b·b·ε), or the first S → ε and the second S → bS → b (a·ε·b·b). Two parse trees, so (B) and (A) are true. abab via S → aSbS needs a w b w' = abab. w = ε, w' = ab works (ab = aεbε). w = ba would need S ⇒ ba, impossible since every a produced is followed later by its b. So only one parse tree and one rightmost derivation (C true). Every CFL is decidable (D false). Answer: (A), (B), (C).

Concept: Ambiguity means two parse trees (equivalently two leftmost or two rightmost derivations) for one string. Membership of any CFL is decidable via CYK.

Subset construction turns an n-state NFA into a DFA with at most 2ⁿ states; the minimal DFA is no larger. With n = 6, at most 2⁶ = 64 states. 32 and 1 are achievable (1 for Σ* or ∅), but 65 and 128 exceed 64. Answer: (B), (D).

Concept: The 2ⁿ blow-up bound of subset construction. The minimal DFA can be much smaller than the NFA, so small numbers are always possible.

Take L₂ = ∅ (regular). Then L₁ ∩ L₂ = ∅ is regular for every L₁, so L₁ can be non-regular, or even not context-free (e.g. {aⁿbⁿcⁿ}). That falsifies (A), (D), and (B) since L₁ ∪ ∅ = L₁. Regular languages are closed under complement, so the complement of L₂ is regular and hence context-free: (C) is always true. Answer: (C).

Concept: Knowing L₁ ∩ L₂ says nothing about the part of L₁ outside L₂. Choosing L₂ = ∅ is the quick counterexample; every regular language is context-free.

B always derives aᵐbᵐ (m ≥ 1): equal numbers of a and b. Each A-rule adds terminals with exactly one more a than b (aaBBAb: 2 a, 1 b; bBabaa: 3 a, 2 b) plus balanced Bs, and every A-derivation ends with bBabaa, so each A-string has a-surplus ≥ 1. S → abaABAbba: the frame aba...bba is balanced (3 a, 3 b), B is balanced, and there are two As, so n₁ - n₂ ≥ 2 and n₁ > n₂ always: (B) true, (A) false. For the ratio, every piece satisfies a ≤ 2b: frame 3 ≤ 6, B m ≤ 2m, aaBBAb terminals 2 ≤ 2, bBabaa terminals 3 ≤ 4. Summing, n₁ ≤ 2n₂ for every string: (D) true, (C) false. (Shortest string: 12 a, 10 b.) Answer: (B), (D).

Concept: Count letters per production instead of generating strings: track the a-minus-b surplus each rule adds. Balanced sub-derivations (B gives aᵐbᵐ) can be ignored for the difference.

M decides L means M halts on every input, accepting exactly the strings in L and rejecting every string not in L. (A) only says it halts (it could decide some other language). (B) alone allows looping on non-members (that is recognising). (C) alone says nothing about members. (D) states both halves, and accepting or rejecting implies halting. Answer: (D).

Concept: Deciding versus recognising: a decider must halt with the correct verdict on every input. The trap is (B), which describes a recogniser that may loop forever on strings outside L.

(A) generates aⁿbⁿ with exactly one derivation per string. (B) id + id * id has two parse trees (+ at root or * at root): ambiguous. (C) 'a' can be derived as S → aS → a or S → Sa → a: two parse trees, ambiguous. (D) is right-linear with one derivation per aⁿ. Answer: (B) and (C).

Concept: Ambiguity means some string has two distinct parse trees. Grammars that can grow on both sides from the same nonterminal (like C) or lack precedence (B) are typical. The trap is thinking C is safe because its language a* is simple.

(A) i - j + k - l = 0: a PDA keeps a signed counter on the stack (+1 for a, c; -1 for b, d), using a marker for sign; accept when it returns to zero. Context-free. (B) i = k and j = l are crossing dependencies (like aⁱbʲcⁱdʲ), not context-free by the pumping lemma. (C) i = l, j = k is nested: S → aSd | T, T → bTc | ε. Context-free. (D) i + j = k + l: push for a and b, pop for c and d. Context-free. Answer: (A), (C) and (D).

Concept: A single stack handles nested or counter-style constraints but not two interleaved (crossing) equalities. The trap is (A), which looks crossing but is really one balanced counter.

A generates a⁺ = {aⁿ | n ≥ 1} and B generates b⁺ = {bⁿ | n ≥ 1}. So S → aaB gives a²bⁿ (n ≥ 1) and S → Abb gives aⁿb² (n ≥ 1). L(G) = {a²bⁿ | n ≥ 1} ∪ {aⁿb² | n ≥ 1}. Answer: (A).

Concept: Read what each non-terminal derives, then combine. The trap is assuming counts are linked (aⁿbⁿ-style) when A and B grow independently.

The given NFA need not be minimal, so a smaller NFA or even a smaller DFA may exist: (A) and (B) are true (they only say "may"). The subset construction gives a DFA with at most 2ⁿ states: (C) true. (D) contradicts (C), since a DFA with at most 2ⁿ states always exists: (D) is false. Answer: (D).

Concept: Subset construction bound: an n-state NFA yields a DFA with at most 2ⁿ states. Watch the question asks for FALSE statements.

L2: push one symbol per a and per b, pop one per c; accept when the stack empties exactly with n, m ≥ 1. Grammar: S → aSc | aXc, X → bXc | bc. So L2 is context-free. L1 = { aᵐbᵐcᵏ | k > m ≥ 1 } needs #a = #b and also #c > #a: two dependent comparisons. Pumping aᵖbᵖcᵖ⁺¹ breaks it: pumping a's and b's up makes them reach the c count, pumping c's down (or only c's) breaks c > a or a = b. Not context-free. Answer: (C).

Concept: One stack can check one linear relation. L2 is a nested match (c count = a's + b's); L1 needs a = b and c > a simultaneously, like aⁿbⁿcⁿ.

Interpret states as the longest suffix matching a prefix of bab: q0 = none, q1 = b, q2 = ba, q3 = bab. Check transitions: from ba, a gives baa (no useful suffix) → q0; from bab, a gives suffix ba → q2, b gives suffix b → q1. So the DFA accepts exactly strings ending in bab. (B) fails: baba contains bab but ends in q2. (A) fails: bab has two b's yet bb is rejected. (D) fails: abab contains aba yet ends in bab and is accepted. Answer: (C).

Concept: Pattern-matching DFAs track the longest suffix that is a prefix of the pattern. "Contains" needs a trap accepting state; returning out of the final state means "ends with".

Every regular language is accepted by a DFA, and a DFA is a DPDA that never uses its stack, so (A) holds. DPDAs accept only the deterministic CFLs, a proper subset of CFLs (for example even-length palindromes are not deterministic), so (B) and (C) fail. Decidable languages such as aⁿbⁿcⁿ are not even context-free, so (D) fails. Answer: (A).

Concept: Hierarchy: regular ⊂ DCFL ⊂ CFL ⊂ decidable. Unlike finite automata, nondeterministic PDAs are strictly more powerful than deterministic ones.

Emptiness of a CFG is decidable: mark generating variables bottom-up and check whether the start symbol is generating. Equivalence of two CFGs, emptiness of the intersection of two CFLs and equality of a CFL with a regular language are all undecidable (the last includes L(G) = Σ*, which is undecidable). Answer: (D).

Concept: For CFLs, membership, emptiness and finiteness are decidable; equivalence, universality, intersection-emptiness and ambiguity are not. The trap is (C): comparing with a regular language does not rescue equivalence.

CFLs: closed under union, not closed under complementation, not closed under intersection. Recursive languages: closed under union, intersection and complementation. Regular languages: closed under all three. (A) fails: recursive languages are closed under complement. (B) holds: CFL-(b), recursive-(a), regular-(c). (C) holds: CFL-(b), recursive-(c), regular-(a). (D) fails: regular languages are closed under complement. Answer: (B) and (C).

Concept: Since several pairings are true, check each pair independently. CFLs fail complement and intersection; recursive and regular classes are closed under all Boolean operations.

(A) = a*b*: regular. (B) Intersecting with {a, b}* forbids c, so m - n = 0 and the language is {aⁿbⁿ | n ≥ 0}: not regular (pumping lemma). (C) A product DFA tracking #a mod 7 and #b mod 9 (63 states) accepts it: regular. (D) Requires #a = #b with no bound, an unbounded comparison: intersecting with a*b* gives {aⁿbⁿ | n ≡ 2 mod 7}, not regular, so (D) is not regular. Answer: (A) and (C).

Concept: Modular counting needs finitely many states; equality of two unbounded counts does not. The trap in (B) is that the intersection forces m = n, leaving aⁿbⁿ.

Track prod(x) mod 7. Every symbol is nonzero mod 7 and 7 is prime, so the product is never 0 and the states are the residues 1 to 6. All are reachable: 3 generates the group (3, 2, 6, 4, 5, 1). Accept only residue 2. Any two residues r ≠ s are distinguishable: take y with r·prod(y) ≡ 2; then s·prod(y) ≢ 2. There is no dead state, since every residue can still reach 2. Minimum DFA: 6 states. Answer: 6.

Concept: Myhill-Nerode with a group structure: multiplication by a fixed symbol permutes the residues, so all reachable states stay distinguishable. The trap is counting 7 states, including an unreachable residue 0.

(A) False: L1 ∩ L2' = ϕ only says L1 ⊆ L2; for example L1 = ϕ and L2 = Σ*. (B) False: take L1 = Σ*, then L1 ∪ L3 = Σ*, regular. (C) True: if L3' were regular, L3 = (L3')' would be regular by closure under complement. (D) True: regular languages are closed under complement and union. Answer: (C), (D).

Concept: Use closure properties, and look for counterexamples like Σ* that swallow a non-regular language. The trap is believing union with a non-regular language must be non-regular.

Each 0 adds 1 and each 1 subtracts 1 from (n₀ − n₁) mod 3: state 1 is 0, states 2 and 5 are 1 (≡ −2), states 3 and 4 are 2 (≡ −1). So L(M) = {w : n₀ − n₁ ≡ 0 mod 3}. States with the same residue are equivalent: 3 ≡ 4 and 2 ≡ 5, so (B) and (C) are false. 2 and 4 differ (input 1 sends 2 to 1, accept, and 4 to 5, reject), so (A) is true. n₀ = n₁ gives residue 0, so (D) is true. Answer: (B), (C).

Concept: Find the invariant each state tracks; equal invariants mean equivalent states. The trap is the question asking for FALSE statements.

In CNF, a rule A → BC increases the number of symbols by one and a rule A → a turns one variable into a terminal. A string of length n needs n − 1 rules of the first kind and n of the second: 2n − 1 steps. Here n = 90, so 179. Answer: 179.

Concept: CNF derivations of a length-n string always take 2n − 1 steps; the number of variables is a distractor. The trap is answering 90 or 89.

Strings of length 0 to 5: 1 + 2 + 4 + 8 + 16 + 32 = 63. r has ϵ plus 0ᵏ and 1ᵏ for k = 1..5: 11 strings. s has 01ᵏ⁻¹ and 10ᵏ⁻¹ for k = 1..5; the length-1 ones (0, 1) are already in r, leaving 2 × 4 = 8 new strings. Union = 19. Neither: 63 − 19 = 44. Answer: 44.

Concept: Count the union with inclusion-exclusion. The trap is double-counting 0 and 1, which are in both r and s.

0 never changes state and 1 toggles between A and B, so the DFA accepts exactly the strings with an odd number of 1s. (A) 0*1(0 + 10*1)*: 0*1 reaches B; each further block 0 stays at B and 10*1 leaves B and returns. It generates exactly the odd-1 strings. (B) generates ε (zero 1s). (C) cannot generate 111. (D) forces a leading 0, so it misses 1. Answer: (A).

Concept: Converting a two-state parity DFA to a regular expression. Testing options on short strings such as ε, 1, 111 and 010 eliminates the wrong ones fast.

Via 1 → 2: the 2-3 loop reads pairs, so ending at 2 accepts (00)*. Reaching 3 reads 0(00)*; then ε to 5, and the 5-4 loop on 1 returns to 5 after 11, giving 0(00)*(11)*. Via 1 → 4: reach 5 with 1, then (11)*: 1(11)*. So L = (00)* + 0(00)*(11)* + 1(11)* = (00)* + (1 + 0(00)*)(11)*. Option (B): 0* = (00)* + 0(00)*, and 0(00)* is already inside 0(00)*(11)*, so (B) equals L. (A) misses 0. (C) misses 0 and wrongly accepts 11. (D) misses 00011. Answer: (B).

Concept: Trace ε-closures: the path through state 3 contributes an odd block of 0s followed by pairs of 1s. Checking short strings such as 0, 011, 00011 separates the options.

Track the number of S symbols in a sentential form. Start with 1. S → aS keeps it, S → aSbS adds one S and one b (and one a), S → c removes an S and adds a c. Every S ends as a c, so nc = 1 + nb: (C) true and (D) false (w = c gives 1 ≠ 0). Each b comes with an a, so na ≥ nb, but w = acbc has na = nb = 1, so (A) false. Since nc − 2 = nb − 1 ≤ na − 1 < na, (B) true. Answer: (B), (C).

Concept: Invariant counting over derivations. Check strict inequalities against the smallest strings (c, acbc) to catch equal cases.

b*ab* contributes exactly one a, and each (ab*ab*) block adds two more, with b's anywhere: L1 = strings over {a,b} with an odd number of a's. Count those of length ≤ 4. Length 1: 1 (a). Length 2: C(2,1) = 2. Length 3: C(3,1) + C(3,3) = 4. Length 4: C(4,1) + C(4,3) = 8. Total = 1 + 2 + 4 + 8 = 15. Answer: 15.

Concept: Recognise the expression as 'odd number of a's'; half of the 2ⁿ strings of each length n ≥ 1 qualify, giving 2ⁿ⁻¹ each.

From s the only useful move is 1 to p (0 goes to the dead state r). At p, reading 0 loops at p, and reading 1 goes to q, from where 1 must follow to return to p (0 goes to r). So from p, the strings that return to p are built from the pieces 0 and 11 in any order. Accepted language: 1(0 + 11)*. (A) forbids trailing 0s such as "10"; (D) forbids "10" too and allows 0s only after 11. Answer: (C).

Concept: Read loops at the final state as alternatives: a 0-self-loop and a 1-1 round trip give (0 + 11)*. The trap is (A) or (D), which force a fixed order of 0s and 11s.

Regular languages are closed under intersection (product automaton), so (A) is correct. CFLs are not: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, which is not context-free, so (B) is incorrect. Recursive languages are closed under intersection (run both deciders, accept if both accept), so (C) is correct. Recursively enumerable languages are closed under intersection (run both recognisers; accept if both accept; if either loops the string is not in the intersection anyway), so (D) is correct. Answer: (A), (C), (D).

Concept: Closure under intersection holds for regular, recursive and RE languages but fails for CFLs. The standard counterexample is the intersection giving aⁿbⁿcⁿ.

X generates any number of a's on the left and b's on the right around one base symbol a or b: L(X) = a*(a + b)b*. S → aSb wraps X in equal numbers of a's and b's: L(S) = {aⁿ w bⁿ : w ∈ a*(a + b)b*, n ≥ 0}. Since aⁿa* = a* and b*bⁿ = b*, this is just a*(a + b)b*, which is regular. Strings like "ba" are not generated, ruling out (A), and (C) wrongly puts the single symbol at the end. Answer: (B).

Concept: The aSb rule looks like it forces equal counts, but X already absorbs arbitrary a's and b's, so the language stays regular. The trap is option (D).

The stack can only be emptied in q (the only move that pops ⊥), and q can be entered only by popping an A. In s, each a pushes one A. Reading b's (s to p, then p) pops one A per b. To reach q from s or p we need an A still on top, so after m a's and n b's we need m - n ≥ 1. In q the remaining A's and ⊥ are popped. The empty string fails (no A to enter q), and m ≥ 1 with n < m works. Language: {aᵐbⁿ | m ≥ 1, n < m}. Answer: (A).

Concept: With empty-stack acceptance, find the only route that pops the bottom marker. Here entering q costs one A, so b's must be strictly fewer than a's; the trap is (B), which allows n = m.

Track the number of consecutive trailing 1s: state 0 (none), state 1 (one 1), state 2 (two 1s); all three are accepting. A 0 returns to state 0; a 1 moves 0 to 1 to 2, and from 2 to a dead state D (three 1s seen), which loops on both symbols. The four states are pairwise distinguishable: from 0, 1, 2 the strings 111, 11, 1 respectively are the shortest that lead to rejection, and D rejects everything. Minimum states: 4. Answer: 4.

Concept: Count states by what must be remembered: the current run of 1s (0, 1, 2) plus a dead state. Forgetting the dead state gives 3, which is the usual mistake for a complete DFA.

Paths that leave q0 and return to it are a b* b (via q1) or b a* a (via q2), so the loops at q0 are (ab*b + ba*a)*. To finish, the string must end in an accepting state: go to q1 and stay (a b*) or go to q2 and stay (b a*). Language = (ab*b + ba*a)*(ab* + ba*), which is option (D) (the union inside the star is commutative). (C) accepts ε and strings ending at q0; (A) and (B) miss mixed loops. Answer: (D).

Concept: State elimination: collect all q0-to-q0 cycles, star them, then append every path to an accepting state. A common trap is allowing the empty suffix, which wrongly accepts strings ending at the non-accepting start.

(A) False: Σ* is recursive, yet its subset HALT is not recursive. (B) True: run recognisers for L and L̄ in parallel; one must accept, so membership is decided. (C) True: every CFL is recursive, and recursive languages are closed under complement. (D) True: regular languages are closed under intersection, and every regular language is deterministic context-free. Answer: (B), (C), (D).

Concept: Closure facts: recursive languages are closed under complement; L and L̄ both RE implies recursive. Subsets inherit nothing - any language is a subset of Σ*.

(A) Equivalence of TMs is undecidable (it is not even RE nor co-RE). (B) Regularity of L(M) is a non-trivial semantic property, undecidable by Rice's theorem. (C) L(M) = Σ* is a non-trivial semantic property, undecidable by Rice's theorem. (D) Decidable: in 1073 steps M reads at most the first 1073 symbols, so it suffices to simulate M for 1073 steps on every string of length at most 1073 - a finite check. Answer: (A), (B), (C).

Concept: Rice's theorem covers properties of the language L(M). A bound on running steps is a property of the machine's behaviour on finitely many relevant inputs, so it is decidable.

L₁: take n as small as allowed and absorb the rest of the a's into w; L₁ = a(a+b)*a (or all of {a,b}* if n = 0 is allowed) - regular either way. L₂: shrink w to a single letter and absorb the rest into x; a string is in L₂ iff it has length ≥ 3 and starts and ends with the same letter: a(a+b)⁺a + b(a+b)⁺b - regular. Regular languages are context-free, so (A), (B), (C) hold and (D) fails. Answer: (A), (B), (C).

Concept: When an unrestricted middle string w or x can swallow the matched parts, the matching constraint disappears. The trap is assuming aⁿ...aⁿ or w...wᴿ always needs a stack.

L₁ = {ww} is not context-free. L₂ and L₃ are deterministic CFLs (one stack comparison each). L₂ ∩ L₃ = {aⁿbⁿcⁿ}, not context-free. The complement of {ww} is context-free (a standard result). (A) True. (B) False, since L₂ is context-free. (C) False, since L₂ ∩ L₃ is not context-free. (D) False, since the complement of L₁ is context-free. Answer: (B), (C), (D).

Concept: CFLs are not closed under intersection; {aⁿbⁿcⁿ} is the classic witness. The complement of {ww} is a CFL even though {ww} is not. Note the question asks for FALSE statements.

The subset construction turns an n-state NFA into a DFA whose states are subsets of the NFA's states, at most 2ⁿ of them. The minimal DFA can be no larger than this DFA, so k ≤ 2ⁿ always. k can be much smaller than n (an NFA can have redundant states), so (A) and (B) fail, and some languages need exactly 2ⁿ states, so (C) fails. Answer: (D) k ≤ 2ⁿ.

Concept: Subset construction gives the 2ⁿ upper bound; there is no lower bound in terms of n because the NFA itself may be non-minimal. The trap is reading the exponential blow-up as always happening (k ≥ 2ⁿ).

(A) False: the complement of the halting language is not RE. (B) True: run the two recognizing TMs in parallel (or one after the other) and accept when both accept. (C) False: recursive languages are a subset of RE, not the other way round. (D) False: each RE language has a Turing machine, and TMs can be encoded as finite strings, so there are only countably many. Answer: (B).

Concept: RE languages are closed under union and intersection but not complement. The number of TMs is countable, so RE is countable. The trap is reversing the subset relation between recursive and RE.

I: the condition is m - n + p - q = 0. A PDA keeps a signed counter on the stack (push for a and c, pop for b and d, switching to a negative marker when the count goes below zero) and accepts if it ends at zero: CFL. II: aᵐbᵐ followed by cᵖdᵖ is the concatenation of two CFLs: CFL. III: requires m = n = p, i.e. it contains the comparison aⁿbⁿcⁿ, which a single stack cannot do (pumping lemma): not CFL. IV: mn = p + q needs multiplication of two counts: not CFL. Answer: (B) I and II only.

Concept: A PDA can do one linear count (including signed sums) or nested matching, but not three-way equality or products. The trap is thinking I needs two stacks because it mentions four counts.

(I) Membership for unrestricted (type-0) grammars is equivalent to TM acceptance: undecidable. (II) Regularity of L(M) for a TM is a non-trivial semantic property: undecidable by Rice's theorem. (III) Equivalence of grammars is undecidable even for context-free grammars, so for arbitrary grammars too. (IV) An NFA accepts a regular language, and every regular language is accepted by some DPDA (a DFA is a DPDA that ignores its stack), so the answer is always yes: decidable. Answer: (D) Only I, II and III are undecidable.

Concept: Rice's theorem for TM language properties; CFG equivalence is undecidable. The trap is (IV): it sounds like a hard question about DPDAs, but its answer is always yes, which makes it trivially decidable.

Accepted strings: ε (at q0) and strings of odd length (ending at q1), so L₁ = {ε} ∪ {0^(2j+1) | j ≥ 0}. L⁰ = {ε}, which differs from L¹. L¹ = L₁ lacks even-length strings of length ≥ 2. L² = L₁ · L₁ contains ε, every odd string (odd · ε) and every even string of length ≥ 2 (odd · odd), so L² = 0*. Then L³ = L² · L₁ = 0*. The smallest k with Lᵏ = Lᵏ⁺¹ is 2. Answer: 2.

Concept: Powers of a language containing ε form an increasing chain; the order is where the chain stabilises. The trap is answering 1 by missing that ε ∈ L₁ means L¹ ⊆ L², and checking whether they are actually equal (they are not, since 00 ∉ L₁).

Each step prepends either a or b, in any order, and ε ends the derivation. So any string over {a, b} of any length, including ε, can be generated, e.g. ba via S ⇒ bS ⇒ baS ⇒ ba. The language is {a, b}*. Answer: (D).

Concept: Reading a right-linear grammar. The trap is (A), which forbids b before a, though the grammar allows a and b in any order.

I: Build the product automaton for the intersection and test reachability of a final state; decidable. II: CFG membership is decidable (convert to CNF and use CYK). III: Equivalence of two CFGs is undecidable. IV: Emptiness of a TM's language is a non-trivial property of RE languages, undecidable by Rice's theorem. Undecidable: III and IV. Answer: (C).

Concept: Know the decidability table: regular languages are closed and decidable for everything; CFLs have decidable membership and emptiness but undecidable equivalence; TM language properties are undecidable.

A string must contain 00 somewhere and 11 somewhere, in either order, possibly far apart. (B) says: anything, then either 00 ... 11 or 11 ... 00, then anything; this captures exactly that. (A) forces 00 and 11 to be adjacent (it misses strings like 001011, where 00 and 11 are separated). (C) is 'contains 00 OR 11'. (D) forces the string to start with 00 or 11 and end with the other. Answer: (B).

Concept: Expressing an AND of two substring conditions with a regex requires both orderings. The trap is (C), which is a union (OR) rather than an intersection.

G1: S generates a* followed by B, and B generates b⁺. So L(G1) = a*b⁺ = {aᵐbⁿ | m ≥ 0 and n > 0}. G2: B generates b*. A generates a* b*. S → aA gives a⁺b*; S → bB gives b⁺. So L(G2) = a⁺b* ∪ b⁺ = all non-empty aᵐbⁿ = {aᵐbⁿ | m > 0 or n > 0}. Answer: (D).

Concept: Translate each nonterminal into a regular expression bottom-up. The trap is missing that G2 cannot generate ε (S has no ε-production) while it can generate strings with only b's.

Acceptance is by final state. Staying in q0, the PDA reads a's and pushes an X for each; since q0 is final, every aⁿ (n ≥ 0) is accepted. On b it pops an X and moves to q1, popping one X per b; when Z is exposed it moves by ε to final q2. So aⁿbⁿ (n ≥ 1) is accepted, and more b's than a's or fewer get stuck or end in non-final q1. L = {aⁿ | n ≥ 0} ∪ {aⁿbⁿ | n ≥ 0}. The machine is deterministic: in each state, for each input/stack-top pair at most one move exists, and the ε-move in q1 is only on Z, where no b-move exists. So L is deterministic context-free. Answer: (D).

Concept: Read acceptance by final state carefully: the accepting start state adds all aⁿ. The trap is (A), forgetting q0 is final, or (B), assuming a union forces nondeterminism.

Y is RE but not recursive, so its complement Ȳ is not RE (if both Y and Ȳ were RE, Y would be recursive). If A ≤m B and B is RE then A is RE; contrapositively, Ȳ ≤m W with Ȳ not RE means W is not RE. X is recursive, so X̄ is recursive. If Z ≤m X̄ and X̄ is recursive, then Z is recursive. So W is not RE and Z is recursive. Answer: (C).

Concept: Reductions transfer decidability downward and undecidability upward; plus the fact that the complement of an RE-but-not-recursive language is not RE. The trap is missing the complement bars on Y and X.

(0 + 1)*(0 + 1)(0 + 1)* is every string with at least one symbol, i.e. all non-empty strings over {0, 1}. The DFA needs a non-accepting start state (seen nothing) and one accepting state reached on any symbol, which loops on 0 and 1. The two states are distinguishable by the empty string. Answer: 2.

Concept: Simplify the regular expression before building the automaton: it is just Σ⁺. A DFA for Σ⁺ needs 2 states. Counting the three factors as three states is the trap.

L₁ = {aⁿbⁿ : n ≥ 0}, which needs unbounded counting and is not regular (pumping lemma). L₂ = (ab)*, a regular expression, so it is regular; the grammar is right-linear. So P is false and Q is true. Answer: (C).

Concept: Recognise the language behind the grammar. Self-embedding (aSb) gives aⁿbⁿ; a right-linear rule (abS) gives a regular language. Judging only by "it is a CFG" is the trap.

I: recursive languages are closed under complement, so L̄₃ is recursive, hence RE; RE is closed under union, so true. II: every CFL is recursive, so L̄₂ is recursive; recursive ∪ recursive is recursive, true. III: L₁* is regular, and regular ∩ CFL is context-free, true. IV: CFLs are not closed under complement, so L̄₂ need not be context-free and the union need not be either; false. Answer: (D) I, II and III only.

Concept: Closure properties across the Chomsky hierarchy. Key facts: recursive is closed under complement, CFL is not; CFL ∩ regular is CFL; every CFL is recursive.

I is false: an NFA may have missing transitions, so a string with no run simply dies. E.g. a one-state accepting NFA over {a, b} with a self-loop only on a accepts a*, not Σ*. II is true: take A = ∅; then A ∩ B = ∅ for every B, which is regular (any finite A also works). Answer: (B) Only II.

Concept: NFAs (and partial DFAs) reject by having no run, not only by ending in a non-accepting state. For II, the empty language is the standard witness.

L₁: a PDA pushes a symbol for each a and each b, then pops one for each c; acceptance when the stack empties exactly. Grammar: S → aSc | aBc, B → bBc | bc. So L₁ is context-free. L₂ needs the count of a to equal the count of b and also c to equal 2n, two dependent comparisons; pumping a string aᵖbᵖc²ᵖ cannot keep all three counts in ratio 1:1:2, so L₂ is not context-free. Answer: (B).

Concept: One stack can match one nested count (a and b against c) but not two independent equalities. aⁿbⁿc²ⁿ behaves like aⁿbⁿcⁿ, the classic non-CFL.

In 2016 steps M reads at most the first 2016 input symbols, so whether M runs at least 2016 steps on input w depends only on w's first 2016 symbols (inputs shorter than that are a finite set too). So simulate M for 2016 steps on every input of length at most 2016, a finite set: this decides both L₁ (some run lasts 2016 steps) and L₂ (all do). L₃ is a non-trivial semantic property of the language of M, undecidable by Rice's theorem. Answer: (C) L₁, L₂ recursive, L₃ not.

Concept: Step-bounded properties are decidable by bounded simulation, since only a finite prefix of input matters. Rice's theorem applies to properties of the language, not of running time; misapplying it to L₁ and L₂ is the trap.

Track the set of active states of the NFA. Start: {q0}. Read 0: q0 -> q0. {q0}. Read 0: {q0}. Read 1: q0 -> q0, q1. {q0, q1}. Read 1: q0 -> q0, q1; q1 -> q2. {q0, q1, q2}. Answer: (A) {q0, q1, q2}.

Concept: Simulating an NFA by tracking the set of current states. The trap is following one path only, or forgetting that q0 keeps looping and stays in the set.

Length 0: ε is in. Length 1: a, b are in. Length 2: aa (a*), ab (a*b*), ba ((ba)*), bb (b*) are all in. Length 3: try bab. After any a* (none here) and b* = b, the remainder ab must match (ba)*a*, which it cannot (it would need to start with b or be all a's). With b* = ε, (ba) consumes ba and the leftover b cannot match a*. So bab is not in the language. Shortest missing string has length 3. Answer: 3.

Concept: Systematic enumeration of short strings against a regular expression. The trap is stopping at length 2 and concluding every short string is covered.

L₁: a DPDA pushes on 0s and pops on 1s, accepting on empty count - deterministic. L₂: push symbols of w until the marker c, then pop and match; the marker tells the machine exactly where the middle is - deterministic. L₃: even-length palindromes have no middle marker, so the PDA must guess the midpoint; this language is context-free but not deterministic CF. Answer: (C) Only L₁ and L₂.

Concept: Deterministic vs non-deterministic CFLs: a centre marker makes palindromes deterministic. The trap is treating wwʳ like wcwʳ.