Notes
15 more interleaved questions across all phases. Focus on avoiding classic GATE traps: dead states, complement of NFA, DCFL union, and syntactic vs semantic TM properties.
Practice questions
- NAT · 2 marks
Over Σ = {0, 1}, what is the number of states in the minimal DFA accepting all strings that have at most two 0s?
Write your answer before opening the key.
- NAT · 1 mark
What is the number of states in the minimal DFA over {0, 1} accepting all strings whose 5th symbol from the end is 1?
Write your answer before opening the key.
- MCQ · 1 mark
A Moore machine M has 5 states and input/output alphabet {0, 1}. When fed an input string of length 20, how many output symbols does M produce?
- 20
- 21
- 25
- 19
- MCQ · 2 marks
Consider the grammar G: S → aA, A → Sb | b. Which statement is TRUE about G and L(G)?
- G is a regular grammar and L(G) is regular
- G is a linear grammar (not regular) and L(G) = {aⁿbⁿ | n ≥ 1} is non-regular
- G is not context-free
- L(G) = a⁺b⁺, which is regular
- MSQ · 2 marks
Let L₁ be a regular language and L₂ be an arbitrary (possibly undecidable) language. Which of the following are GUARANTEED to be regular?
- Prefix(L₁)
- L₁ / L₂ (right quotient of L₁ by L₂)
- L₁ ∩ L₂
- A subset L₃ ⊆ L₁
- MCQ · 2 marks
Consider the language L = { aibjck | i = j or j = k }. Which statement is correct?
- L is a DCFL and has an unambiguous CFG
- L is a CFL, not a DCFL, and is inherently ambiguous
- L is not a Context-Free Language
- L is unambiguous because it is the union of two DCFLs
- NAT · 1 mark
A CFG G₁ in Greibach Normal Form (GNF) derives a string w of length 10 in S₁ steps, and a CFG G₂ in Chomsky Normal Form (CNF) derives the same string w in S₂ steps. What is S₂ − S₁?
Write your answer before opening the key.
- MSQ · 2 marks
Which of the following languages are Context-Free Languages (CFLs)?
- { aⁿbⁿcᵐdᵐ | n, m ≥ 0 }
- { aⁿbᵐcᵐdⁿ | n, m ≥ 0 }
- { aⁿbᵐcⁿdᵐ | n, m ≥ 0 }
- { w ∈ {a,b}* | w ≠ w'w' for any w' } (complement of copy language)
- MCQ · 2 marks
Suppose a language L satisfies the pumping lemma for regular languages. What can we conclude about L?
- L is definitely regular
- L is definitely context-free
- Nothing — L may or may not be regular
- L must be infinite
- MCQ · 1 mark
In the Chomsky hierarchy, non-contracting grammars (where every production α → β satisfies |α| ≤ |β|, except possibly S → ε with S not on any RHS) generate exactly:
- Context-Free Languages (Type 2)
- Context-Sensitive Languages (Type 1)
- Recursive Languages
- Recursively Enumerable Languages (Type 0)
- MSQ · 2 marks
Which of the following languages are Recursively Enumerable (RE)?
- A_TM = { ⟨M, w⟩ | M accepts w }
- HALT_TM = { ⟨M, w⟩ | M halts on w }
- L_ne = { ⟨M⟩ | L(M) ≠ ∅ }
- L_e = { ⟨M⟩ | L(M) = ∅ }
- MCQ · 2 marks
What is the decidability status of the Post Correspondence Problem (PCP)?
- Undecidable for every alphabet Σ
- Decidable when |Σ| = 1, and undecidable when |Σ| ≥ 2
- Decidable when |Σ| ≤ 2, and undecidable when |Σ| ≥ 3
- Decidable for all finite domino sets
- NAT · 2 marks
How many distinct complete DFAs can be formed with state set Q = {q₀, q₁}, input alphabet Σ = {0, 1, 2}, and fixed start state q₀?
Write your answer before opening the key.
- MCQ · 2 marks
Let G₁ and G₂ be arbitrary Context-Free Grammars and R be a Regular expression. Which of the following problems is DECIDABLE?
- Is L(G₁) = L(G₂)?
- Is L(G₁) ⊆ L(G₂)?
- Is L(G₁) ⊆ L(R)?
- Is L(R) ⊆ L(G₁)?
- MCQ · 1 mark
The existence of the Universal Turing Machine UTM demonstrates that:
- Every language over Σ is decidable
- A single fixed Turing machine can simulate any arbitrary Turing machine M given its encoding ⟨M, w⟩
- The halting problem is decidable
- Nondeterministic TMs are faster than deterministic TMs
Answer key
Reveal answers when you’re ready
- 4 — Counts of 0s seen so far: 0 (accept), 1 (accept), 2 (accept), and ≥ 3 (dead/trap state, reject). Total = k + 2 = 4 states.
- 32 — For "k-th symbol from the end is 1" over a binary alphabet, the minimal DFA has 2^k = 2⁵ = 32 states.
- B — A Moore machine outputs one symbol for its initial state plus one after each of the 20 transitions: n + 1 = 21 symbols.
- A: 20 is the output length of a Mealy machine.
- C: Number of states is not added to input length.
- D: Never n − 1.
- B — Every production has at most one variable on the RHS (linear), but S → aA is right-linear while A → Sb is left-linear. Mixing sides generates {aⁿbⁿ | n ≥ 1}, which is not regular.
- A: Mixing left- and right-linear rules is not allowed in a regular grammar.
- C: Single variable on LHS means G is a valid CFG.
- D: Counts of a and b are locked together: each S → aA → aSb adds one a and one b.
- AB — Prefix(L₁) and the right quotient L₁ / L₂ are always regular whenever L₁ is regular (we just change the set of accepting states of L₁’s DFA, though finding which states are in F′ may not be constructive if L₂ is undecidable, the DFA still exists!). Intersection with or subset of a regular language can be non-regular (e.g. L₁ = Σ*, L₂ = {aⁿbⁿ}).
- C: Σ* ∩ {aⁿbⁿ} = {aⁿbⁿ}, not regular.
- D: {aⁿbⁿ} ⊆ Σ* is a non-regular subset of a regular language.
- B — L is the classic inherently ambiguous CFL: every CFG for L must generate strings of the form aⁿbⁿcⁿ in at least two ways (once via the i=j branch, once via the j=k branch). Since every DCFL is unambiguous, L cannot be a DCFL.
- A: L is neither a DCFL nor unambiguous.
- C: L is the union of two CFLs, hence a CFL.
- D: Union of two DCFLs is not necessarily unambiguous or DCFL.
- 9 — In GNF, S₁ = n = 10. In CNF, S₂ = 2n − 1 = 19. Therefore S₂ − S₁ = 19 − 10 = 9.
- ABD — A is concatenation of two aⁿbⁿ-type languages; B is nested wrapping; D is the complement of {ww}, which is a well-known CFL! C has crossing dependencies (a’s with c’s and b’s with d’s), so it is not a CFL.
- C: {aⁿbᵐcⁿdᵐ} requires cross-serial matching, which exceeds one stack (not a CFL).
- C — The pumping lemma is a necessary condition for regularity, NOT a sufficient condition. Some non-regular (and even non-CFL) languages satisfy the pumping property, and all finite languages satisfy it vacuously.
- A: Converse fallacy.
- B: Non-CFLs can also satisfy the regular pumping property.
- D: Every finite language satisfies the pumping lemma vacuously (pick p > max length).
- B — Type 1 (Context-Sensitive) grammars are defined equivalently by context-sensitive rules αAγ → αβγ (β ≠ ε) or by non-contracting rules |α| ≤ |β|; they correspond to Linear Bounded Automata.
- A: Type 2 requires a single variable on the LHS.
- C: No standard Chomsky grammar number corresponds to REC alone.
- D: Type 0 has no length restriction on α → β.
- ABC — A_TM and HALT_TM are recognized by simulating M on w. L_ne = {⟨M⟩ | L(M) ≠ ∅} is recognized by dovetailing (running M on all strings in Σ* in parallel stages and accepting as soon as one string is accepted). L_e is the complement of L_ne; since L_ne is RE but undecidable, L_e is NOT RE.
- D: E_TM = {⟨M⟩ | L(M) = ∅} is co-RE, not RE.
- B — Over a 1-letter (unary) alphabet, PCP reduces to checking whether a linear Diophantine system of lengths has a positive solution, which is decidable. Over any alphabet of size ≥ 2, PCP is undecidable.
- A: Unary PCP is decidable.
- C: Binary PCP (|Σ| = 2) is already undecidable.
- D: A PCP instance always has a finite set of dominoes, yet the problem is undecidable.
- 256 — |Q| = 2, |Σ| = 3. The transition function δ : Q × Σ → Q has 2 × 3 = 6 entries, each with 2 choices: 2⁶ = 64 transition tables. There are 2² = 4 choices for the accepting set F ⊆ Q. Total = 64 × 4 = 256.
- C — L(G₁) ⊆ L(R) ⇔ L(G₁) ∩ L(R)̅ = ∅. Since R is regular, L(R)̅ is regular; CFL ∩ Regular is a CFL (with an effectively constructible CFG), and emptiness of a CFG is decidable! By contrast, L(R) ⊆ L(G₁) with R = Σ* asks whether L(G₁) = Σ* (universality of CFG), which is undecidable.
- A: CFG equivalence is undecidable.
- B: CFG inclusion is undecidable.
- D: Taking R = Σ* reduces CFG universality (Σ* ⊆ L(G₁)) to this problem, so it is undecidable.
- B — U_TM takes ⟨M, w⟩ as data on its tape and simulates M step by step on w — the stored-program computer principle.
- A: Uncountably many languages are undecidable.
- C: The halting problem is undecidable.
- D: U_TM is about universality/simulation, not NTM speed.