Introduction
Full-length GATE Theory of Computation mock test across Phases 0–5.
- Time limit: 90 minutes (timer starts when you click Start and saves automatically).
- Structure: 30 questions — Q1 to Q14 carry 1 mark each; Q15 to Q30 carry 2 marks each (total = 46 marks).
- Marking scheme:
- MCQ (Multiple Choice — single correct): +1 mark (or +2 marks) for correct; −1/3 mark for a wrong 1-mark MCQ and −2/3 mark for a wrong 2-mark MCQ.
- MSQ (Multiple Select — one or more correct): Full marks only if ALL correct options and NO wrong options are selected; 0 negative marking.
- NAT (Numerical Answer Type): Type a number; 0 negative marking.
- Weighting: Matches GATE CSE weightage — highest emphasis on Finite Automata & Minimization, Regular Expressions, Language Classification, Closure Properties, and Decidability / Rice’s Theorem.
Final test questions
- MCQ · 1 mark
Which of the following statements about the empty language ∅ and the language {ε} over Σ = {0, 1} is FALSE?
- |∅| = 0 and |{ε}| = 1
- ∅* = {ε}
- ∅ · {0, 1}* = {ε}
- {ε} · {0, 1}* = {0, 1}*
- NAT · 1 mark
Over Σ = {a, b}, what is the number of states in the minimal DFA that accepts all strings of length at least 3 (i.e., |w| ≥ 3)?
Write your answer before opening the key.
- NAT · 1 mark
Over Σ = {0, 1}, what is the number of states in the minimal DFA accepting all strings whose 3rd symbol from the end is 0?
Write your answer before opening the key.
- MCQ · 1 mark
A Mealy machine M₁ and a Moore machine M₂ both operate over input alphabet Σ = {0, 1} and output alphabet Δ = {a, b}. On an input string w of length 15, the lengths of the output strings produced by M₁ and M₂ are, respectively:
- 15 and 15
- 15 and 16
- 16 and 15
- 16 and 16
- MCQ · 1 mark
Which of the following strings is NOT generated by the regular expression
(a + ab)*?- ε
- aab
- aba
- abb
- MCQ · 1 mark
The right-linear grammar G with productions S → 0S | 1A, A → 0A | 1A | ε generates which regular language over {0, 1}?
- All strings containing at least one 1
- All strings starting with 1
- All strings ending with 1
- 0*1*
- MSQ · 1 mark
Which of the following operations ALWAYS preserve regularity when applied to regular languages L₁ and L₂?
- Set difference L₁ − L₂
- Reversal L₁ᴿ
- Inverse homomorphism h⁻¹(L₁)
- Infinite union L₁ ∪ L₂ ∪ L₃ ∪ … of regular languages
- NAT · 1 mark
A Context-Free Grammar G is in Chomsky Normal Form (CNF). How many derivation steps are required to derive any terminal string w ∈ L(G) of length 11?
Write your answer before opening the key.
- MCQ · 1 mark
Which of the following inclusions between language families is FALSE?
- Every Regular language is a Deterministic Context-Free Language (DCFL)
- Every DCFL is a Context-Free Language (CFL)
- Every CFL is a DCFL
- Every DCFL has an unambiguous Context-Free Grammar
- MCQ · 1 mark
Which automaton model recognizes exactly the family of Context-Sensitive Languages (Type 1 in the Chomsky hierarchy)?
- Deterministic Push-Down Automaton (DPDA)
- Nondeterministic Push-Down Automaton (NPDA)
- Linear Bounded Automaton (LBA)
- Multi-tape Turing Machine
- MCQ · 1 mark
If a language L and its complement L̅ are both Recursively Enumerable (RE), then L is necessarily:
- Regular
- Context-Free
- Recursive (Decidable)
- Finite
- MCQ · 1 mark
Why must there exist languages over Σ = {0, 1} that are NOT Recursively Enumerable?
- Because some Turing machines have too few states
- Because the set of all Turing machines is countably infinite, whereas the set of all languages P(Σ*) is uncountable
- Because Σ* is uncountable
- Because every RE language is finite
- MCQ · 1 mark
By Rice’s theorem, which of the following properties of a Turing machine M is DECIDABLE?
- L(M) = ∅
- L(M) is finite
- L(M) is Recursively Enumerable
- L(M) contains at least one palindrome
- MSQ · 1 mark
For an arbitrary Context-Free Grammar G, which of the following problems are DECIDABLE?
- Is L(G) = ∅? (Emptiness)
- Is L(G) finite? (Finiteness)
- Is w ∈ L(G) for a given string w? (Membership)
- Is L(G) = Σ*? (Universality)
- NAT · 2 marks
Consider a complete DFA M with 6 states {A, B, C, D, E, F} over Σ = {0, 1}, start state A, and accepting states F_acc = {C, D, E}. The transitions are:
A: 0→B, 1→C | B: 0→A, 1→D | C: 0→E, 1→F | D: 0→E, 1→F | E: 0→E, 1→F | F: 0→F, 1→F.
How many states does the minimal DFA equivalent to M have?Write your answer before opening the key.
- NAT · 2 marks
Over Σ = {a, b}, let L = { w ∈ {a, b}* | |w|a ≡ 0 (mod 2) and w ends with
b}. What is the number of states in the minimal DFA accepting L?Write your answer before opening the key.
- NAT · 2 marks
An NFA N over Σ = {0, 1} has 4 states {q₀, q₁, q₂, q₃}, start state q₀, accepting state q₃, and transitions:
q₀: 0→{q₀, q₁}, 1→{q₀} | q₁: 0→{q₂}, 1→{q₂} | q₂: 0→{q₃}, 1→∅ | q₃: 0→∅, 1→∅.
How many reachable states does the DFA produced by the subset construction on N have?Write your answer before opening the key.
- MSQ · 2 marks
Which of the following regular expressions over Σ = {0, 1} denote the language of all strings having an even number of 1s (including zero 1s)?
- 0*(10*10*)*
- (0 + 10*1)*
- (0*10*1)*0*
- 0*(10*1)*0*
- MCQ · 2 marks
Consider a 2-state DFA over {a, b} with start state q₀ and accepting state q₁. The transitions are: q₀ —a→ q₁, q₀ —b→ q₀, q₁ —a→ q₀, q₁ —b→ q₁. Which regular expression describes L(M)?
- b*a(b + ab*a)*
- (b + ab*a)*
- b*a(a + bb*)*
- (a + b)*a
- MSQ · 2 marks
Consider the following languages over Σ = {a, b}:
L₁ = { anbm | n ≥ 1, m ≥ 1, n · m is even }
L₂ = { w ∈ {a, b}* | every prefix u of w satisfies ||u|a − |u|b| ≤ 2 }
L₃ = { anbn | n ≥ 0 } ∪ { anbm | n ≠ m }
L₄ = { anb2n | n ≥ 1 }
Which of these languages are REGULAR?- L₁
- L₂
- L₃
- L₄
- MCQ · 2 marks
Match the languages X = { anbmcn | n, m ≥ 1 }, Y = { anbncm | n, m ≥ 1 } ∪ { ambncn | n, m ≥ 1 }, and Z = { anbmcndm | n, m ≥ 1 } to their smallest language classes:
- X: DCFL, Y: CFL (not DCFL), Z: CSL (not CFL)
- X: CFL (not DCFL), Y: DCFL, Z: CSL (not CFL)
- X: DCFL, Y: DCFL, Z: CFL (not DCFL)
- X: Regular, Y: CFL (not DCFL), Z: CSL (not CFL)
- MCQ · 2 marks
Consider the Context-Free Grammar G with productions
S → aSbS | bSaS | ε. What is L(G), and is G ambiguous?- L(G) = { w ∈ {a,b}* | |w|ₐ = |w|_b }, and G is ambiguous
- L(G) = { w ∈ {a,b}* | |w|ₐ = |w|_b }, and G is unambiguous
- L(G) = { (ab)ⁿ | n ≥ 0 }, and G is unambiguous
- L(G) = { w ∈ {a,b}* | w = wᴿ }, and G is ambiguous
- NAT · 2 marks
A deterministic PDA starts in state q₀ with Z on the stack. On reading
a, it pushes two X’s onto the stack (replacing top T by XXT). On readingb, it pops one X from the stack. Suppose the PDA reads the prefixaaab. Including the bottom marker Z, how many symbols are on the stack immediately afteraaabis read?Write your answer before opening the key.
- MSQ · 2 marks
Let L₁ be a Deterministic Context-Free Language (DCFL) and L₂ be a Context-Free Language (CFL). Which of the following are ALWAYS Context-Free Languages?
- L₁̅ (complement of L₁)
- L₂ᴿ (reversal of L₂)
- L₁̅ ∪ L₂
- L₂ − L₁
- MCQ · 2 marks
Which of the following rows correctly states the closure properties of the language classes under Intersection (∩) and Complement (¬)?
- DCFL: (∩ No, ¬ Yes) | CFL: (∩ No, ¬ No) | REC: (∩ Yes, ¬ Yes) | RE: (∩ Yes, ¬ No)
- DCFL: (∩ Yes, ¬ Yes) | CFL: (∩ No, ¬ No) | REC: (∩ Yes, ¬ Yes) | RE: (∩ Yes, ¬ No)
- DCFL: (∩ No, ¬ Yes) | CFL: (∩ Yes, ¬ No) | REC: (∩ Yes, ¬ Yes) | RE: (∩ No, ¬ Yes)
- DCFL: (∩ No, ¬ No) | CFL: (∩ No, ¬ Yes) | REC: (∩ Yes, ¬ No) | RE: (∩ Yes, ¬ No)
- MSQ · 2 marks
Which of the following statements about Context-Sensitive Languages (CSLs) and Recursive (REC) languages are TRUE?
- Every Context-Free Language is a Context-Sensitive Language (ignoring ε or allowing S → ε)
- Every Context-Sensitive Language is Recursive (decidable)
- CSLs are closed under union, intersection, and complement
- Emptiness is decidable for Context-Sensitive Grammars
- MSQ · 2 marks
Consider the following four languages of Turing machine encodings:
L₁ = { ⟨M⟩ | M takes at least 50 steps on input ε }
L₂ = { ⟨M⟩ | L(M) contains at least 50 strings }
L₃ = { ⟨M⟩ | M has at most 50 states }
L₄ = { ⟨M⟩ | L(M) = L(M₀) } (where M₀ is a fixed TM that never halts on any input)
Which of these languages are DECIDABLE?- L₁
- L₂
- L₃
- L₄
- MCQ · 2 marks
Let L₁ = { ⟨M⟩ | L(M) ≠ ∅ }, L₂ = { ⟨M⟩ | L(M) = ∅ }, and L₃ = { ⟨M₁, M₂⟩ | L(M₁) = L(M₂) }. Which option correctly classifies L₁, L₂, and L₃?
- L₁ ∈ RE − REC, L₂ ∈ co-RE − REC, L₃ is neither RE nor co-RE
- L₁ ∈ REC, L₂ ∈ REC, L₃ ∈ co-RE − REC
- L₁ ∈ co-RE − REC, L₂ ∈ RE − REC, L₃ ∈ co-RE − REC
- L₁ ∈ RE − REC, L₂ ∈ RE − REC, L₃ is neither RE nor co-RE
- MCQ · 2 marks
Suppose A ≤m B and B ≤m C via computable mapping reductions. If A is known to be undecidable and C is known to be Recursively Enumerable (RE), which statement MUST be true about B?
- B is Recursively Enumerable, but NOT decidable (B ∈ RE − REC)
- B is decidable (B ∈ REC)
- B is neither RE nor co-RE
- B is co-RE, but NOT RE
- NAT · 2 marks
Over Σ = {a, b}, how many strings of length 5 belong to the language of the regular expression
(a + b)*aa(a + b)*(i.e., strings of length 5 that containaaas a substring)?Write your answer before opening the key.
Answer key
Reveal answers when you’re ready
- C — Concatenating any language with ∅ yields ∅ (since there is no string in ∅ to pair with), so ∅ · {0, 1}* = ∅, not {ε}.
- A: True: ∅ has 0 strings, while {ε} has 1 string (of length 0).
- B: True: by definition, L⁰ = {ε} is always included in L*.
- D: True: {ε} is the identity element for language concatenation.
- 4 — For |w| ≥ k, the minimal DFA tracks lengths 0, 1, 2, and ≥ 3 (accepting sink): k + 1 = 3 + 1 = 4 states.
- 8 — For the k-th symbol from the end over a 2-symbol alphabet, the minimal DFA requires 2^k = 2³ = 8 states.
- B — A Mealy machine outputs one symbol per transition (length n = 15), whereas a Moore machine outputs one symbol for the initial state plus one after each transition (length n + 1 = 16).
- A: Moore outputs n + 1 symbols.
- C: Swaps Mealy and Moore output lengths.
- D: Mealy outputs n symbols, not n + 1.
- D — Every b in (a + ab)* comes from the block "ab", so every b must be immediately preceded by an a. In "abb", the second b is preceded by b, so "abb" cannot be generated.
- A: Zero repetitions of (a + ab)* yields ε.
- B: Generated as a · ab.
- C: Generated as ab · a.
- A — S generates 0* followed by 1A, and A generates (0 + 1)*. Thus L(G) = 0*1(0 + 1)*, which is the set of all binary strings containing at least one 1.
- B: Leading 0s are allowed via S → 0S.
- C: After the first 1, A → 0A | ε allows trailing 0s.
- D: A allows 1s after 0s (e.g. 101).
- ABC — Regular languages are closed under set difference, reversal, and inverse homomorphism. They are NOT closed under infinite union (e.g. ⋃_{n≥0} {aⁿbⁿ} = {aⁿbⁿ | n ≥ 0}).
- D: Infinite union of finite (hence regular) sets {aⁿbⁿ} produces a non-regular language.
- 21 — In CNF, deriving a string of length n ≥ 1 always requires 2n − 1 = 2(11) − 1 = 21 steps.
- C — DCFL is a strict subset of CFL (DCFL ⊊ CFL); for example, {wwᴿ | w ∈ {a,b}*} and {aⁱbʲcᵏ | i = j or j = k} are CFLs that are not DCFLs.
- A: True: a DFA is a DPDA that ignores its stack.
- B: True: every DPDA is also an NPDA.
- D: True: determinism yields a unique accepting computation and hence an unambiguous grammar.
- C — Linear Bounded Automata (nondeterministic TMs whose head cannot move beyond the input markers) recognize exactly the Context-Sensitive Languages.
- A: Recognizes DCFLs.
- B: Recognizes CFLs (Type 2).
- D: Recognizes Recursively Enumerable languages (Type 0).
- C — By the complementation theorem, L ∈ REC iff both L ∈ RE and L̅ ∈ RE (run both recognizers in parallel; one must halt on every input w).
- A: There are decidable languages (like aⁿbⁿcⁿ) that are not regular.
- B: aⁿbⁿcⁿ is decidable (hence L and L̅ are RE) but not context-free.
- D: Infinite decidable languages satisfy L, L̅ ∈ RE.
- B — Each TM has a finite encoding over a finite alphabet, so there are only countably many (ℵ₀) TMs and RE languages, while P(Σ*) has uncountably many (2^ℵ₀) languages.
- A: Even allowing arbitrarily many states, the set of all TMs is countable.
- C: Σ* is countably infinite.
- D: RE languages can be infinite.
- C — Every Turing machine recognizes a Recursively Enumerable language by definition! Thus "L(M) is RE" is a trivial semantic property (true for all TMs) and is trivially decidable (always output YES).
- A: Non-trivial semantic property → undecidable.
- B: Non-trivial semantic property → undecidable.
- D: Non-trivial semantic property → undecidable.
- ABC — Emptiness, finiteness, and membership (via CYK) are decidable for all CFGs. Universality L(G) = Σ* is undecidable for CFGs.
- D: Universality of CFGs is undecidable.
- 3 — All 6 states are reachable from A. Partition P₀ = {{A, B, F}, {C, D, E}}. In {C, D, E}, every state goes to E on 0 and F on 1, so {C, D, E} never splits. In {A, B, F}, F goes to F on 1 (non-accepting) while A and B go to C and D (accepting), splitting into {A, B} and {F}. On 0, A and B swap within {A, B}; on 1, both go to {C, D, E}. Thus P₁ = {{A, B}, {C, D, E}, {F}} is stable: 3 states.
- 3 — When #a is odd, whether the last symbol was a or b does not affect any future continuation (in both cases, reading a goes to "even a, ends in a" and reading b stays in "odd a"). Thus all odd-#a prefixes merge into a single state O, while even-#a prefixes split into E_nb (start, does not end in b) and E_b (accepting, ends in b). All 3 states {E_nb, E_b, O} are pairwise distinguishable (by ε and b). Total = 3 states.
- 6 — Let us trace the lazy subset construction starting from {q₀}:
1. {q₀}: on 0 → {q₀,q₁}; on 1 → {q₀}.
2. {q₀,q₁}: on 0 → {q₀,q₁,q₂}; on 1 → {q₀,q₂}.
3. {q₀,q₁,q₂}: on 0 → {q₀,q₁,q₂,q₃}; on 1 → {q₀,q₂}.
4. {q₀,q₂}: on 0 → {q₀,q₁,q₃}; on 1 → {q₀}.
5. {q₀,q₁,q₂,q₃}: on 0 → {q₀,q₁,q₂,q₃}; on 1 → {q₀,q₂}.
6. {q₀,q₁,q₃}: on 0 → {q₀,q₁,q₂}; on 1 → {q₀,q₂}.
All transitions now land in these 6 subsets. Total reachable DFA states = 6. - ABC — A, B and C each generate exactly the binary strings with an even number of 1s (checked against every string up to length 9). D allows 0s only at the ends and inside a pair, never between two pairs: “11011” (four 1s) has its middle 0 between the first and second pair, so D cannot generate it.
- D: Cannot generate "11011" because the middle 0 lies between two (10*1) pairs where D allows no 0s.
- A — M flips between q₀ and q₁ on every a and stays in the same state on b, so L(M) is the set of strings with an odd number of a’s. Using Arden: q₀ = ε + q₀b + q₁a = (ε + q₁a)b* = b* + q₁ab*; then q₁ = q₀a + q₁b = b*a + q₁(b + ab*a) ⇒ q₁ = b*a(b + ab*a)*.
- B: Describes q₀ (even number of a’s), not q₁.
- C: Allows "aa" (two a’s) via b*a · a, which is rejected.
- D: Requires ending in a and allows even number of a’s (e.g. "aa").
- ABC — L₁: n·m is even iff n is even OR m is even (only parities needed ⇒ regular). L₂: the running difference #a − #b is restricted to {−2, −1, 0, 1, 2} plus a dead state (6 states ⇒ regular). L₃: union of n = m and n ≠ m over a*b* is all of a*b* (regular). L₄ requires unbounded 1:2 counting (DCFL, not regular).
- D: {aⁿb²ⁿ | n ≥ 1} is a non-regular DCFL.
- A — X pushes a’s, skips b’s, and pops a’s on c’s deterministically (DCFL). Y is the inherently ambiguous union of two DCFLs, which requires nondeterminism (CFL, not DCFL). Z has crossing dependencies between a–c and b–d, so it fails the CFL pumping lemma and is a CSL (not CFL).
- B: Swaps X and Y.
- C: Y is not a DCFL and Z is not a CFL.
- D: X requires unbounded counting and is not regular.
- A — G generates all strings over {a,b} with an equal number of a’s and b’s. Moreover, G is ambiguous: for w = abab, there are two distinct parse trees (S ⇒ aSbS ⇒ abS ⇒ ab aSbS ⇒ abab via matching the first a with the first b, OR S ⇒ aSbS ⇒ a bSaS bS ⇒ abab via matching the first a with the last b).
- B: w = abab has two distinct parse trees in G, so G is ambiguous (even though the language itself is a DCFL and has another unambiguous grammar).
- C: G also generates aabb, baab, etc.
- D: ab ∈ L(G) is not a palindrome.
- 6 — Start: 1 symbol (Z). Three a’s push 3 × 2 = 6 X’s (stack has 6 X’s + Z = 7 symbols). One b pops 1 X, leaving 5 X’s + 1 Z = 6 symbols on the stack.
- ABC — A: DCFL is closed under complement, so L₁̅ is a DCFL (hence a CFL). B: CFL is closed under reversal. C: Since L₁̅ is a CFL and CFLs are closed under union, L₁̅ ∪ L₂ is always a CFL. D: L₂ − L₁ = L₂ ∩ L₁̅ is the intersection of a CFL and a DCFL, which need not be a CFL (for example, {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}).
- D: L₂ − L₁ = L₂ ∩ L₁̅; since DCFLs and CFLs are not closed under intersection with a DCFL, this can produce aⁿbⁿcⁿ (not a CFL).
- A — DCFL is closed under complement (✓) but not intersection (✗); CFL is closed under neither (✗, ✗); REC is closed under both (✓, ✓); RE is closed under intersection (✓) but not complement (✗).
- B: DCFL is not closed under intersection ({aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}).
- C: CFL is not closed under ∩, and RE is closed under ∩ but not ¬.
- D: DCFL is closed under ¬, CFL is not, and REC is closed under ¬.
- ABC — CFL ⊊ CSL ⊊ REC, and CSLs are closed under union, intersection, and complement (Immerman–Szelepcsényi theorem). However, emptiness of a CSG/LBA is undecidable.
- D: Emptiness of a Context-Sensitive Grammar (or LBA) is undecidable.
- AC — L₁: Run M on ε for 50 steps; if it has not halted by step 49, it takes at least 50 steps (decidable!). L₃: Count states in the encoding ⟨M⟩ (syntactic, decidable!). L₂: Non-trivial semantic property of L(M) (undecidable by Rice). L₄: Since L(M₀) = ∅, L₄ asks whether L(M) = ∅, which is undecidable by Rice.
- B: |L(M)| ≥ 50 is a non-trivial semantic property of L(M) → undecidable (it is RE, not REC).
- D: L(M) = L(M₀) = ∅ is E_TM, which is undecidable.
- A — L₁ is recognized by dovetailing M on all strings in Σ* until one accepts (RE, not REC). L₂ is the complement of L₁, so L₂ ∈ co-RE − REC. L₃ (equivalence of two TMs) is neither RE nor co-RE.
- B: All three are undecidable.
- C: Swaps L₁ and L₂, and L₃ is not even co-RE.
- D: If both L₁ and L₂ were RE, they would be decidable.
- A — Since A ≤_m B and A is undecidable, B must be undecidable (B ∉ REC). Since B ≤_m C and C ∈ RE, B must be in RE. Combining both gives B ∈ RE − REC.
- B: If B were decidable, A ≤_m B would make A decidable.
- C: B ≤_m C ∈ RE forces B ∈ RE.
- D: If B were co-RE in addition to RE, B would be decidable, contradicting A undecidable.
- 19 — Total strings of length 5 over {a, b} is 2⁵ = 32. The number of strings of length 5 with NO "aa" is the Fibonacci number F₇ = 13 (since for lengths 0,1,2,3,4,5 the counts are 1, 2, 3, 5, 8, 13). Therefore, the number of strings of length 5 that DO contain "aa" is 32 − 13 = 19.