Notes
15 interleaved GATE-style questions spanning Phases 0–5. Do not look at the topic tags until after you answer — part of the exam skill is recognizing which phase a question belongs to.
Practice questions
- NAT · 1 mark
Over Σ = {a, b}, what is the number of states in the minimal DFA that accepts all strings starting with
aband having length at least 2?Write your answer before opening the key.
- MCQ · 1 mark
Let w =
gate27(6 distinct characters). How many distinct substrings (including ε and w itself) does w have?- 21
- 22
- 64
- 36
- MSQ · 2 marks
Which of the following regular expressions over {a, b} are equivalent to
(a + b)*?- (a*b*)*
- a*(ba*)*
- (a* + b*)*
- a* + b*
- MCQ · 2 marks
Consider L₁ = { w x wR | w, x ∈ {a, b}+ } and L₂ = { w wR | w ∈ {a, b}+ }. Which statement is correct?
- Both L₁ and L₂ are regular
- L₁ is regular, and L₂ is a CFL but not a DCFL
- L₁ is a DCFL (not regular), and L₂ is a CFL
- Neither L₁ nor L₂ is regular
- NAT · 1 mark
A context-free grammar G is in Chomsky Normal Form (CNF). To derive a terminal string w of length 25, how many production steps are used in any derivation of w?
Write your answer before opening the key.
- MCQ · 2 marks
In a DFA with start state P and sole accepting state Q, the incoming state equations are P = ε + Pa + Qb and Q = Pb + Qa. Which regular expression represents the accepted language Q?
- a*b(a + ba*b)*
- (a + bb)*b
- a*b(a + bb)*
- b(a + ba*b)*
- MSQ · 2 marks
Let L be a Deterministic Context-Free Language (DCFL) and R be a Regular language. Which of the following languages are GUARANTEED to be DCFLs?
- L̅ (complement of L)
- L ∩ R
- L ∪ R
- L* (Kleene star of L)
- MCQ · 1 mark
Which class of languages is accepted by Deterministic Push-Down Automata (DPDAs) that accept by empty stack?
- All Context-Free Languages
- All Deterministic Context-Free Languages
- Exactly the prefix-free DCFLs
- Exactly the Regular Languages
- NAT · 2 marks
When running the CYK membership algorithm on a string of length n = 9, how many table cells (substring spans) are computed in total?
Write your answer before opening the key.
- MCQ · 2 marks
Which of the following machines is strictly LESS powerful than a standard single-tape deterministic Turing machine?
- A Turing machine whose head can only move Left or Right (no Stay move)
- A Nondeterministic Turing Machine
- A Linear Bounded Automaton (LBA)
- A Push-Down Automaton with two independent stacks
- MSQ · 2 marks
Which of the following statements about Recursive (REC) and Recursively Enumerable (RE) languages are TRUE?
- REC is closed under complement, union, and intersection
- RE is closed under union, intersection, and Kleene star
- RE is closed under complement
- If L ∈ RE and L̅ ∈ RE, then L ∈ REC
- MCQ · 1 mark
Over Σ = {0, 1}, let S₁ be the set of all strings Σ*, S₂ be the set of all Turing machines, and S₃ be the set of all languages over Σ. Which statement is true?
- S₁, S₂, and S₃ are all countably infinite
- S₁ and S₂ are countably infinite, while S₃ is uncountable
- Only S₁ is countable; S₂ and S₃ are uncountable
- S₁ is finite, S₂ is countable, S₃ is uncountable
- MCQ · 2 marks
Which of the following problems about a Turing machine M is DECIDABLE?
- Whether L(M) contains at least 10 strings
- Whether L(M) is a regular language
- Whether M visits more than 5 states when run on the empty string ε within 100 steps
- Whether L(M) = Σ*
- MCQ · 2 marks
Suppose L₁ ≤m L₂ (L₁ is mapping-reducible to L₂). Which implication is ALWAYS valid?
- If L₁ is undecidable, then L₂ is undecidable
- If L₂ is undecidable, then L₁ is undecidable
- If L₁ is decidable, then L₂ is decidable
- If L₂ is not RE, then L₁ is not RE
- MSQ · 2 marks
Which of the following decision problems are DECIDABLE?
- Equivalence of two DFAs M₁ and M₂
- Emptiness of a Context-Free Grammar G
- Membership of a string w in a Context-Sensitive Grammar G
- Emptiness of a Linear Bounded Automaton (LBA)
Answer key
Reveal answers when you’re ready
- 4 — States: q₀ (start, ε), q₁ (read a), q₂ (read ab, accepting sink looping on a,b), and D (dead state for starting with b or reading aa). Total = 4 states.
- B — All 6 characters are distinct, so there are n(n+1)/2 = 6·7/2 = 21 non-empty substrings plus 1 for the empty string ε = 22.
- A: 21 is the count of non-empty substrings; it forgets ε.
- C: 2⁶ = 64 is the number of subsequences, not substrings.
- D: n² = 36 overcounts.
- ABC — (a*b*)*, a*(ba*)*, and (a* + b*)* are all standard identities for (a + b)*. Option D only generates strings of all a’s or all b’s (misses "ab").
- D: a* + b* does not contain "ab".
- B — In L₁, taking |w| = 1 lets x absorb everything between the first and last symbol, so L₁ = a(a+b)⁺a + b(a+b)⁺b (regular). L₂ is the language of non-empty even-length palindromes, which is a CFL but not a DCFL.
- A: L₂ requires unbounded memory with an unmarked midpoint, so it is not regular.
- C: L₁ is regular because w can be chosen of length 1.
- D: L₁ is regular.
- 49 — In CNF, deriving a string of length n ≥ 1 always takes 2n − 1 = 2(25) − 1 = 49 steps.
- A — From P = ε + Pa + Qb = (ε + Qb) + Pa, Arden gives P = (ε + Qb)a* = a* + Qba*. Substitute into Q: Q = (a* + Qba*)b + Qa = a*b + Q(a + ba*b). Apply Arden to Q: Q = a*b(a + ba*b)*.
- B: Ignores the loop on P with a and on Q with a.
- C: Misses a* between b and b in the return loop.
- D: Requires the first symbol to be b, missing strings starting with a.
- ABC — DCFLs are closed under complement, intersection with regular languages, and union with regular languages (by product of DPDA and DFA). DCFLs are NOT closed under Kleene star.
- D: DCFLs are not closed under Kleene star (nor concatenation or general union).
- C — Once an empty-stack DPDA empties its stack to accept u, it cannot continue on any extension uv, so it can only accept prefix-free DCFLs.
- A: Even final-state DPDAs cannot accept all CFLs.
- B: Non-prefix-free DCFLs like a* cannot be accepted by empty stack deterministically.
- D: aⁿbⁿ (n ≥ 1) is accepted by an empty-stack DPDA and is not regular.
- 45 — The triangular CYK table has n(n + 1)/2 = 9 × 10 / 2 = 45 cells.
- C — An LBA restricts the tape head to the cells occupied by the input (linear space) and recognizes Context-Sensitive Languages (CSLs), which is a strict subset of RE. All other options are equivalent to a standard TM.
- A: Stay can be simulated by moving Right then Left.
- B: NTM and DTM recognize the exact same class (RE).
- D: A 2-stack PDA simulates a TM tape (left of head in stack 1, right in stack 2).
- ABD — REC is closed under complement, ∪, ∩. RE is closed under ∪, ∩, *, concatenation, but NOT complement. If both L and L̅ are RE, running their recognizers in parallel decides L.
- C: RE is not closed under complement; A_TM is RE but its complement is not.
- B — Strings in Σ* can be listed in canonical order (countable), every TM has a finite encoding string (countable), and P(Σ*) has cardinality 2^ℵ₀ (uncountable by Cantor’s diagonalization).
- A: P(Σ*) is uncountable.
- C: Every TM is encoded by a finite string, so S₂ is countable.
- D: Σ* is countably infinite, not finite.
- C — Simulating M on ε for at most 100 steps and counting visited states always terminates in 100 steps (a bounded syntactic/step-execution property, not a semantic property of L(M)). A, B, D are non-trivial semantic properties of L(M) and are undecidable by Rice’s theorem.
- A: Non-trivial property of L(M) → undecidable by Rice.
- B: Non-trivial property of L(M) → undecidable by Rice.
- D: Universality of TMs → undecidable by Rice.
- A — If L₂ were decidable, then composing the reduction f with L₂’s decider would decide L₁. By contrapositive, L₁ undecidable ⇒ L₂ undecidable.
- B: A trivial decidable L₁ (like {0}) can reduce to an undecidable L₂.
- C: Knowing the easier side is decidable says nothing about L₂.
- D: Backwards: L₂ ∈ RE ⇒ L₁ ∈ RE, so L₁ ∉ RE ⇒ L₂ ∉ RE.
- ABC — DFA equivalence, CFG emptiness, and CSL/LBA membership are all decidable. Emptiness of an LBA (CSL) is undecidable.
- D: LBA emptiness is undecidable (proven via accepting computation histories of a TM).