CS Atlas GATE 2027
TOC course
0 / 91 complete

TOC/Phase 6 · Integration & Final Test

Revision 6.3 · Item 90 of 91

GATE pattern drill

Read at your own pace. Try the questions before opening the answers.

On this page

Notes

Over 85% of GATE Theory of Computation marks come from 12 recurring question patterns. For each pattern below, learn the recognition trigger, follow the numbered speed-method, and study the worked example before attempting the 12 drill questions at the bottom.

1Pattern 1: Minimal DFA State Counting

Trigger: “What is the number of states in the minimal DFA over Σ accepting L = { … }?”

Fastest solving method:

  1. Check the standard formula table first: starts with w (k+2), ends with w (k+1), contains w (k+1), length/count = k or ≤ k (k+2), length/count ≥ k (k+1), mod n (n), k-th from start (k+2), k-th from end (2k).
  2. If compound (#a mod m and/or #b mod n): multiply the independent state trackers (m · n), then check if any states merge (e.g. an accepting sink or dead state absorbs sub-cases).
  3. If custom: use Myhill–Nerode (“distinct futures”): list the minimal pieces of information a prefix must remember to decide future continuations, and always ask whether a dead state is reachable.
Worked ExampleOver Σ = {a, b}, find the number of states in the minimal DFA accepting strings that contain at least one a and at most one b.

Solution: Track (#a ∈ {0, ≥1}) × (#b ∈ {0, 1, ≥2}). Once #b ≥ 2, the string is hopeless regardless of #a, so all (#b ≥ 2) cases collapse into 1 dead state D. For #b ∈ {0, 1} and #a ∈ {0, ≥1}, we have 2 × 2 = 4 live states: (0,0), (≥1,0)*, (0,1), (≥1,1)*. All 4 have distinct futures (separated by ε, a, b, ab) and D is separated by everything. Total = 4 + 1 = 5 states.

2Pattern 2: NFA → DFA State Counting (Subset Construction)

Trigger: Given an NFA table/diagram (or a description with nondeterministic guessing), find the number of states in the equivalent DFA produced by subset construction.

Fastest solving method:

  1. Never answer 2n blindly: 2n is only the upper bound; GATE asks for the number of reachable subset-states from ECLOSE(q₀).
  2. Do lazy worklist expansion: start with S₀ = ECLOSE({q₀}). For each new subset S and each input symbol, compute δ(S, a). Add only newly discovered subsets to your list.
  3. Watch for ∅ and universal self-loops: if q₀ loops to itself on every symbol in Σ, every reachable subset contains q₀, so at most 2n−1 subsets can ever be reached and ∅ never appears! If ∅ is reached, count it as a state (the dead state).
Worked ExampleAn NFA over {0, 1} has 3 states {p, q, r} with start p and transitions: p —0,1→ p; p —1→ q; q —0→ r (no moves from r). How many states does the subset-construction DFA have?

Solution: Start with {p}.
• From {p}: on 0 → {p}; on 1 → {p, q} (new).
• From {p, q}: on 0 → {p, r} (new); on 1 → {p, q}.
• From {p, r}: on 0 → {p}; on 1 → {p, q}.
Worklist closes! Reachable subsets: {p}, {p, q}, {p, r} = 3 states (language: ends with 10).

3Pattern 3: Regex Equivalence & Language Identification

Trigger: “Which of the following regular expressions is equivalent to R?” or “Which regex represents language L?”

Fastest solving method:

  1. Test length 0, 1, 2 strings first (The 15-Second Sieve): Check ε, then a, b, then aa, ab, ba, bb. Any option that accepts a forbidden short string or misses a required short string is eliminated immediately.
  2. Check structural invariants: Does the option force the string to start/end with a fixed symbol? Does it forbid "aa" before "b"?
  3. Apply algebraic identities for remaining contenders: use (r + s)* = (r*s*)* = r*(sr*)* and shifting (rs)*r = r(sr)*.
Worked ExampleWhich regex over {0, 1} represents all strings where every 0 is immediately followed by 1? (A) (1 + 01)*   (B) (01)*1*   (C) 1*(01)*   (D) (1 + 01)*(0 + ε)

Solution: Test short strings in L: ε ✓, 1 ✓, 01 ✓, 101 ✓, 0101 ✓; while 0 ∉ L and 00 ∉ L.
• (D) generates "0", which violates the rule → eliminate D.
• (B) cannot generate "101" (all 01s must come before 1s) → eliminate B.
• (C) cannot generate "011" → eliminate C.
• (A) builds strings from blocks "1" and "01" in any order: every 0 is paired with an immediate 1, and every such string decomposes into "1" and "01" blocks. Answer: (A).

4Pattern 4: Regular-or-Not Fast Test

Trigger: Given 2 to 4 set-builder languages, identify which ones are regular.

Fastest solving method:

  1. Check for disguised finiteness or collapse: Is there an upper bound like n ≤ 106? (Finite ⇒ Regular!) Does a free middle variable x ∈ Σ+ absorb the constraint, as in {wxwR}? (Collapses to first = last symbol ⇒ Regular!)
  2. Check if the memory needed is bounded: Modular arithmetic (n ≡ m mod k), parities, bounded prefix differences (|#a − #b| ≤ 3), or substring counts like #ab = #ba need only finitely many states ⇒ Regular.
  3. Check for unbounded exact comparisons or non-periodic unary sets: #a = #b, n ≥ m, n ≠ m, ww, wwR, an², aprime ⇒ Not Regular.
Worked ExampleWhich are regular? L₁ = { ambn | m + n is odd }, L₂ = { ambn | m − n = 2 }, L₃ = { u v uR | u, v ∈ {0,1}+ }.

Solution: L₁ tracks only parity of length (2 states × a*b* order) ⇒ Regular. L₂ ties m and n by an exact unbounded equation m = n + 2 ⇒ Not regular. L₃ has u, v ∈ {0,1}+: choosing |u| = 1 reduces it to "starts and ends with the same bit and length ≥ 3" ⇒ Regular. Answer: L₁ and L₃.

5Pattern 5: Language Classification Ladder (Reg / DCFL / CFL / CSL / REC / RE)

Trigger: Classify a language into its smallest Chomsky/automata class.

Fastest solving method:

  1. Step 1 (Bounded?): Finite / mod k / free middle → Regular.
  2. Step 2 (One stack, deterministic trigger?): Single comparison (anbn, wcwR, #a = #b, aibjck with i = j + k) or sequential/nested pairs (anbncmdm, anbmcmdn) → DCFL.
  3. Step 3 (One stack, needs a guess?): Unmarked palindrome (wwR), OR of two comparisons (i = j or j = k; anbn ∪ anb2n), complement of ww → CFL (not DCFL).
  4. Step 4 (Two+ independent comparisons / copy / crossing / nonlinear unary?): anbncn, ww, anbmcndm, i < j < k, an², aprime → CSL (not CFL).
  5. Step 5 (TM description language?): Halting / acceptance / non-emptiness → RE (not REC); emptiness of L(M) → co-RE (not RE); equivalence, totality, regularity of L(M) → neither.
Worked ExampleClassify L = { anbmcn+m | n, m ≥ 0 } and M = { anbmcn·m | n, m ≥ 0 }.

Solution: Rewrite L as anbmcmcn: a DPDA pushes A for each a, pushes B for each b, pops B for the first m c’s, then pops A for the remaining n c’s — no guessing! So L is a DCFL. M requires multiplication n·m, which needs repeating a count m times (two-way tape movement) — so M is a CSL (not CFL).

6Pattern 6: Closure-Property Combination MSQs

Trigger: “L₁ ∈ Class X, L₂ ∈ Class Y. Which class is L₁ op L₂ guaranteed to belong to?”

Fastest solving method:

  1. Convert both operands to the common / larger class, UNLESS the operation is intersection/difference with a Regular language (every class from DCFL to RE is closed under ∩ Regular!).
  2. Check the Master Closure Table for that class and operation.
  3. Remember the 4 classic traps: (a) DCFL ∪ DCFL is CFL, not necessarily DCFL; (b) CFL ∩ CFL is CSL/REC, not necessarily CFL; (c) Complement of CFL is CSL/REC, not CFL; (d) Complement of RE is co-RE, not RE.
Worked ExampleLet L₁ be a DCFL, L₂ be a CFL, and R be Regular. What is the smallest class guaranteed to contain (L₁̅ ∪ L₂) ∩ R?

Solution: L₁ is a DCFL ⇒ L₁̅ is a DCFL (DCFL closed under complement) ⇒ L₁̅ is also a CFL. Union with CFL L₂ gives a CFL (CFL closed under ∪). Intersecting that CFL with Regular R gives a CFL (CFL closed under ∩ Regular).

7Pattern 7: Decidability Table MSQs

Trigger: “Which of the following problems are decidable for class X?”

Fastest solving method:

  1. Regular: EVERYTHING is decidable.
  2. CFL: ONLY M E F (Membership, Emptiness, Finiteness) are decidable. Everything else (Equivalence, Universality, Inclusion, Regularity, Ambiguity, Disjointness) is undecidable! (Exception: L(G) ⊆ R for regular R reduces to emptiness of L(G) ∩ R̅, which IS decidable.)
  3. DCFL: M, E, F plus Universality (via complement) and Equivalence (Sénizergues) and Regularity are decidable; Inclusion and Disjointness are undecidable.
  4. CSL & REC: ONLY Membership is decidable. Emptiness, Finiteness, Equivalence, Universality are all undecidable.
  5. RE: NOTHING in the table is decidable (even membership is only semi-decidable/RE).
Worked ExampleDecidable or undecidable for a CFG G: (i) L(G) = {a, b}*?   (ii) L(G) ∩ {anbn} = ∅?   (iii) L(G) ∩ a*b* = ∅?

Solution: (i) Universality of CFG → Undecidable. (ii) Emptiness of intersection of two CFLs → Undecidable. (iii) a*b* is regular, so L(G) ∩ a*b* is a CFL whose grammar we can construct, and CFL emptiness is decidable → Decidable!

8Pattern 8: Rice’s Theorem Applicability

Trigger: Given several languages of TM encodings {⟨M⟩ | …}, decide which are decidable vs undecidable.

Fastest solving method:

  1. Test 1 — Is it semantic or syntactic/bounded? Does the condition talk ONLY about the set of accepted strings L(M), or does it mention states, tape cells, head moves, or a fixed step bound k?
    • If it bounds steps (e.g. “halts on w within 50 steps”) or counts states/symbols in ⟨M⟩ → DECIDABLE (Rice does NOT apply).
    • If it asks about unbounded head/state behavior (e.g. “ever enters state q”) → Rice doesn’t apply directly, but it is usually undecidable by direct reduction from ATM (unless trivial like “moves right on step 1”).
  2. Test 2 — Is the semantic property trivial? Is it true for NO RE languages (∅) or ALL RE languages? For example, “L(M) is recursively enumerable” is true for ALL TMs → DECIDABLE (always yes).
  3. Otherwise (non-trivial semantic property of L(M)): Rice’s theorem applies → UNDECIDABLE.
Worked ExampleClassify as decidable or undecidable: (i) {⟨M⟩ | M has ≥ 10 states}   (ii) {⟨M⟩ | L(M) contains ε and M halts on ε within 20 steps}   (iii) {⟨M⟩ | L(M) is decidable}   (iv) {⟨M⟩ | L(M) is RE}.

Solution: (i) Syntactic (inspect ⟨M⟩) → Decidable. (ii) Bounded simulation (run M on ε for 20 steps) → Decidable. (iii) Non-trivial semantic property (∅ is decidable, ATM is not) → Undecidable by Rice. (iv) Trivial semantic property (every TM’s language is RE!) → Decidable.

9Pattern 9: Reduction Direction & RE / co-RE Deduction

Trigger: Questions on A ≤m B, or classifying whether {⟨M⟩ | …} is RE, co-RE, or neither.

Fastest solving method:

  1. Arrow = "is at most as hard as": Read A ≤m B as A ≤ B. If the bigger one (B) is easy (REC / RE / co-RE), the smaller one (A) is also easy. If the smaller one (A) is hard (undecidable / not RE / not co-RE), the bigger one (B) is also hard.
  2. One witness vs all strings (RE vs co-RE test):
    • If verifying "yes" only needs finding one finite accepting run (e.g. "M accepts w", "M halts on w", "L(M) ≠ ∅", "|L(M)| ≥ 3") → RE (not REC) via dovetailing.
    • If "yes" is the exact negation of a dovetailing property (e.g. "M does not halt on w", "L(M) = ∅", "|L(M)| ≤ 2") → co-RE (not RE).
    • If "yes" requires checking infinitely many inputs (e.g. "L(M) = Σ*", "M halts on ALL inputs", "L(M) is infinite/regular/CFL") → Neither RE nor co-RE (REGTM and CFLTM belong here too).
Worked ExampleIs L = { ⟨M⟩ | |L(M)| ≥ 2 } in RE, co-RE, REC, or neither?

Solution: Dovetail M on all strings in Σ*; as soon as 2 distinct strings are accepted, halt and accept ⟨M⟩! So L is in RE. By Rice’s theorem L is undecidable, so L ∉ REC, which also means L ∉ co-RE. Answer: RE but not REC (and not co-RE).

10Pattern 10: CNF / GNF Step & Conversion Counts

Trigger: Counting steps in CNF/GNF derivations, parse tree nodes, or new rules after grammar cleanup.

Fastest solving method:

  1. CNF derivation of w (|w| = n ≥ 1): Total steps = 2n − 1. Binary rules (A → BC) used = n − 1. Terminal rules (A → a) used = n.
  2. GNF derivation of w (|w| = n ≥ 1): Total steps = n (one terminal generated per step).
  3. CNF parse tree height h (where h counts edges from root to terminal leaf): Max yield length = 2h−1 (since the last level is A → a). If height counts variable levels/binary splits k, max yield = 2k.
Worked ExampleIn a CNF grammar, a derivation of string w uses 14 applications of rules of the form A → BC. What is |w| and what is the total number of steps in the derivation?

Solution: Number of binary rules = n − 1 = 14 ⇒ |w| = n = 15. Total derivation steps = 2(15) − 1 = 29.

11Pattern 11: PDA & TM Transition Tracing

Trigger: Given explicit δ transitions of a PDA or TM, find the accepted language, final tape content, or halting state.

Fastest solving method:

  1. For a PDA: Write the net stack change per symbol: e.g. a pushes 2 A’s (+2), b pops 1 A (−1). Set total change = 0: 2(#a) − #b = 0 ⇒ #b = 2(#a). Then check phase order (states) and boundary conditions (is ε accepted? must at least one b be read?).
  2. For a TM: Trace on tiny inputs (n = 1, 2) by writing configurations (e.g. q0 a b □). Identify each state’s macro-role ("scan right to blank", "zig-zag matching one a with one b", "flip 0↔1", "add 1 in binary").
Worked ExampleA TM over {0, 1} starts at the leftmost bit: q₀ reads 0→0,R and 1→1,R; on □ it moves L to q₁. In q₁: 1→0,L (stay in q₁); 0→1,S (go to qacc); □→1,S (go to qacc). What does the TM compute?

Solution: q₀ scans to the right end of the binary number. q₁ scans right-to-left, turning trailing 1s into 0s until the first 0 is flipped to 1 (or □ becomes 1) and halts. That is binary increment (adding 1 to a binary number)!

12Pattern 12: Counting Strings of Length n in a Language

Trigger:NAT question: “How many strings of length n over Σ belong to L?”

Fastest solving method:

  1. Direct combinatorics (fixed positions / counts): If k positions are fixed and n − k are free over m symbols → mn−k. If parity is fixed (even number of a’s over {a,b}) → 2n−1.
  2. Inclusion–Exclusion (OR of two patterns): |A ∪ B| = |A| + |B| − |A ∩ B|.
  3. DFA path-counting recurrence (for forbidden substrings): Write a tiny table of (state, length 0, 1, 2, …, n) where each column is the sum of incoming states from the previous column. For "no two consecutive a’s", total strings = Fibonacci Fn+2 (1, 2, 3, 5, 8, 13, 21, …).
Worked ExampleOver Σ = {0, 1}, how many strings of length 6 start with 01 OR end with 10?

Solution: Let A = starts with 01 (first 2 bits fixed, 4 free ⇒ 2⁴ = 16). Let B = ends with 10 (last 2 bits fixed, 4 free ⇒ 2⁴ = 16). A ∩ B = starts with 01 AND ends with 10 (4 bits fixed, middle 2 free ⇒ 2² = 4). By inclusion–exclusion: 16 + 16 − 4 = 28.

Practice questions

  1. NAT · 2 marks

    What is the number of states in the minimal DFA over {a, b} that accepts all strings containing aba as a substring?

    Write your answer before opening the key.

  2. NAT · 2 marks

    An NFA over {a, b} has 3 states {1, 2, 3}, start state 1, and transitions: 1 —a,b→ 1; 1 —a→ 2; 2 —a,b→ 3 (no moves from 3). How many reachable states does the subset-construction DFA have?

    Write your answer before opening the key.

  3. MCQ · 2 marks

    Which regular expression over {a, b} is equivalent to (a + b)*b(a + b)* (strings containing at least one b)?

    1. a*b(a + b)*
    2. (a + b)*ba*
    3. Both (A) and (B)
    4. a*ba*
  4. MSQ · 2 marks

    Which of the following languages over {a, b} are REGULAR?

    1. { w ∈ {a,b}* | #(ab) = #(ba) }
    2. { aⁿbⁿ | 0 ≤ n ≤ 500 }
    3. { aⁿbᵐ | n ≡ m (mod 5) }
    4. { aⁿbᵐ | n ≠ m }
  5. MCQ · 2 marks

    What is the smallest language class containing L = { aⁿbⁿ | n ≥ 1 } ∪ { aⁿb²ⁿ | n ≥ 1 }?

    1. Regular
    2. DCFL
    3. CFL (not DCFL)
    4. CSL (not CFL)
  6. MCQ · 2 marks

    If L₁ is a Context-Free Language and L₂ is a Regular Language, which of the following is NOT necessarily a Context-Free Language?

    1. L₁ ∩ L₂
    2. L₁ − L₂
    3. L₂ − L₁
    4. L₁ / L₂
  7. MSQ · 2 marks

    Which of the following decision problems are UNDECIDABLE?

    1. Whether a CFG G is ambiguous
    2. Whether L(G) = Σ* for a CFG G
    3. Whether L(M₁) = L(M₂) for two DPDAs M₁ and M₂
    4. Whether L(M) = ∅ for a Turing machine M
  8. MSQ · 2 marks

    Which of the following languages of Turing machine encodings are DECIDABLE?

    1. { ⟨M⟩ | M halts on ε within 50 steps }
    2. { ⟨M⟩ | M has at most 12 states }
    3. { ⟨M⟩ | L(M) = ∅ }
    4. { ⟨M⟩ | L(M) is a Recursive language }
  9. MCQ · 2 marks

    Suppose A ≤m B and A is NOT Recursively Enumerable (A ∉ RE). Which statement MUST be true?

    1. B is not Recursively Enumerable (B ∉ RE)
    2. B is Recursively Enumerable
    3. B is decidable
    4. B̅ is Recursively Enumerable
  10. NAT · 1 mark

    In a CNF grammar, a derivation of a terminal string w applies terminal productions (of the form A → a) 18 times. How many total derivation steps (including binary rules A → BC) were used to derive w?

    Write your answer before opening the key.

  11. MCQ · 2 marks

    A PDA pushes one X for each a read in state q₀, switches to q₁ on reading c (without changing the stack), pops one X for each b read in q₁, and accepts when the stack has only Z₀ left. What language does it accept?

    1. { aⁿcbⁿ | n ≥ 0 }
    2. { aⁿbⁿ | n ≥ 0 }
    3. { wcwᴿ | w ∈ {a,b}* }
    4. { aⁿcbᵐ | n, m ≥ 0 }
  12. NAT · 2 marks

    Over Σ = {a, b}, how many strings of length 5 start with a AND end with b?

    Write your answer before opening the key.

Answer key

Reveal answers when you’re ready
  1. 4 — For "contains w" where |w| = k, the minimal DFA always has k + 1 = 3 + 1 = 4 states (no dead state needed).

    Review lesson 1.1.3

  2. 4 — Start: {1}. From {1}: a → {1,2}, b → {1}. From {1,2}: a → {1,2,3}, b → {1,3}. From {1,2,3}: a → {1,2,3}, b → {1,3}. From {1,3}: a → {1,2}, b → {1}. Reachable subsets: {1}, {1,2}, {1,2,3}, {1,3} = 4 states (language: 2nd symbol from end is a).

    Review lesson 1.2.3

  3. C — a*b(a + b)* splits on the FIRST b; (a + b)*ba* splits on the LAST b. Both describe all strings with at least one b.
    • A: True, but (B) is also equivalent.
    • B: True, but (A) is also equivalent.
    • D: Describes strings with exactly one b.

    Review lesson 2.1.2

  4. ABC — A holds iff |w| ≤ 1 or first symbol = last symbol (regular); B is finite (regular); C tracks (n − m) mod 5 in 5 states (regular). D is non-regular (complement ∩ a*b* = aⁿbⁿ).
    • D: Unbounded inequality comparison; not regular.

    Review lesson 2.4.4

  5. C — Each component is a DCFL, so their union is a CFL. However, a DPDA cannot deterministically know whether to pop 1 or 2 b’s per a without guessing, so L is a CFL but not a DCFL.
    • A: Requires unbounded counting.
    • B: DCFLs are not closed under union; this union requires nondeterminism.
    • D: It is generated by S → A | B, A → aAb | ab, B → aBbb | abb (a CFG).

    Review lesson 3.4.4

  6. C — L₂ − L₁ = L₂ ∩ L̅₁. Taking L₂ = Σ* gives Σ* − L₁ = L̅₁, the complement of a CFL, which is NOT necessarily a CFL! By contrast, L₁ ∩ L₂, L₁ − L₂ = L₁ ∩ L̅₂, and L₁ / L₂ are all CFLs.
    • A: CFL ∩ Regular is always a CFL.
    • B: L₁ − L₂ = L₁ ∩ L̅₂, and L̅₂ is regular, so it is a CFL.
    • D: CFLs are closed under quotient with a regular language.

    Review lesson 3.4.1

  7. ABD — CFG ambiguity, CFG universality, and TM emptiness are all undecidable. Equivalence of two DPDAs (DCFLs) is decidable by Sénizergues’ theorem.
    • C: Equivalence of DCFLs is decidable.

    Review lesson 5.5

  8. AB — A is decided by running M on ε for 50 steps; B is decided by counting states in ⟨M⟩. C and D are non-trivial semantic properties of L(M) and are undecidable by Rice’s theorem.
    • C: Emptiness of L(M) is undecidable.
    • D: Whether L(M) is recursive is a non-trivial semantic property → undecidable.

    Review lesson 5.4

  9. A — If B were RE, then A ≤_m B would imply A ∈ RE (simulate the reduction f(w) and run B’s recognizer). Therefore B cannot be RE.
    • B: Would force A ∈ RE.
    • C: Would force A decidable.
    • D: B could be neither RE nor co-RE.

    Review lesson 5.3

  10. 35 — 18 terminal rules means |w| = n = 18. The total number of steps in CNF is 2n − 1 = 2(18) − 1 = 35.

    Review lesson 3.2.2

  11. A — It reads aⁿ in q₀ (pushing n X’s), reads a single c to enter q₁, and reads bⁿ in q₁ (popping all n X’s).
    • B: Requires c in the middle.
    • C: Only a’s are allowed before c and only b’s after c.
    • D: Counts of a and b must be equal for Z₀ to be exposed at the end.

    Review lesson 3.3.1

  12. 8 — Position 1 is fixed to a and position 5 is fixed to b. The remaining 3 middle positions each have 2 choices: 2³ = 8.

    Review lesson 2.1.1

ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.