CS701 — Theory of Computation: Midterm & Finalterm Solved MCQs and Subjective

This solved paper covers CS701 — Theory of Computation for Virtual University of Pakistan students, with midterm (Lectures 1–22) and finalterm (Lectures 23–45) questions solved with answers. It includes 10 midterm MCQs, 10 finalterm MCQs, 5 midterm subjective questions and 5 finalterm subjective questions — 30 questions in total — covering theory of computation, finite automata, regular languages, context-free grammars and Turing machines. Every answer was solved independently and cross-checked against the VU handout, with the handout lecture cited under each question; handout page numbers are being added as they are verified. Use the Take the CS701 quiz link below to practise all 20 MCQs interactively with a live score counter. See the Solved MCQs page and the midterm and finalterm mega hubs for solved papers for every subject. Compiled and verified by Virtual Ustaad. Last updated: 6 November 2026.

1. Midterm Solved MCQs

Q1. Hilbert's Tenth Problem asked for an algorithm to decide whether a Diophantine equation has a solution in integers. What was the eventual answer?

A) Yes — such an algorithm was found by Hilbert himself
B) No — Matiyasevich proved no such algorithm exists; the problem is unsolvable
C) Yes — but only for equations with two unknowns
D) The problem is still open

Correct answer: B — No — Matiyasevich proved no such algorithm exists; the problem is unsolvable

Reference: VU handout, Lectures 1–22 — History of computing; Hilbert's Tenth Problem. Page — not confirmed in source.

Status: Verified

Q2. The Halting Problem — deciding whether a given program halts on a given input — is:

A) Decidable by simulation with a time limit
B) Decidable for all programs except recursive ones
C) Undecidable: no algorithm solves it for all programs and inputs
D) Decidable, but only on finite tapes

Correct answer: C — Undecidable: no algorithm solves it for all programs and inputs

Reference: VU handout, Lectures 1–22 — History of computing; Halting Problem. Page — not confirmed in source.

Status: Verified

Q3. A deterministic finite automaton (DFA) is formally defined as a:

A) 3-tuple (Q, Σ, δ)
B) 5-tuple (Q, Σ, δ, q₀, F)
C) 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
D) 4-tuple (Q, Σ, δ, F)

Correct answer: B — 5-tuple (Q, Σ, δ, q₀, F)

Reference: VU handout, Lectures 1–22 — Automata theory: finite automata. Page — not confirmed in source.

Status: Verified

Q4. An NFA with n states can always be converted into an equivalent DFA with at most:

A) n states
B) n² states
C) 2^n states
D) 2n states

Correct answer: C — 2^n states

Reference: VU handout, Lectures 1–22 — Automata theory: NFA to DFA conversion. Page — not confirmed in source.

Status: Verified

Q5. The class of regular languages is closed under:

A) Union only
B) Intersection only
C) Union, intersection and complement
D) None of these

Correct answer: C — Union, intersection and complement

Reference: VU handout, Lectures 1–22 — Automata theory: closure properties of regular languages. Page — not confirmed in source.

Status: Verified

Q6. By the Myhill–Nerode theorem, a language L is regular if and only if:

A) It is accepted by some NFA
B) The number of equivalence classes of the indistinguishability relation for L is finite
C) It is generated by some regular expression
D) It has a pumping length

Correct answer: B — The number of equivalence classes of the indistinguishability relation for L is finite

Reference: VU handout, Lectures 1–22 — Automata theory: properties of regular languages. Page — not confirmed in source.

Status: Verified

Q7. The language {a^n b^n : n ≥ 0} is:

A) Regular
B) Context-free but not regular
C) Not context-free
D) Finite

Correct answer: B — Context-free but not regular

Reference: VU handout, Lectures 1–22 — Automata theory: non-regular languages; context-free languages. Page — not confirmed in source.

Status: Verified

Q8. Which grammar generates the language {a^n b^n : n ≥ 0}?

A) S → aS | bS | ε
B) S → aSb | ε
C) S → abS | ε
D) S → aSb | a

Correct answer: B — S → aSb | ε

Reference: VU handout, Lectures 1–22 — Context-free grammars. Page — not confirmed in source.

Status: Verified

Q9. A context-free grammar is ambiguous if:

A) It has more than one non-terminal
B) Some string in its language has two or more different parse trees (leftmost derivations)
C) It generates a regular language
D) It contains a nullable non-terminal

Correct answer: B — Some string in its language has two or more different parse trees (leftmost derivations)

Reference: VU handout, Lectures 1–22 — Context-free grammars: ambiguity. Page — not confirmed in source.

Status: Verified

Q10. A pushdown automaton (PDA) differs from a finite automaton in that it also has:

A) An infinite tape
B) A stack for unbounded auxiliary memory
C) Two input heads
D) A random-access memory

Correct answer: B — A stack for unbounded auxiliary memory

Reference: VU handout, Lectures 1–22 — Automata theory: pushdown automata. Page — not confirmed in source.

Status: Verified

2. Finalterm Solved MCQs

Q1. A (single-tape) Turing machine is formally defined as a:

A) 5-tuple (Q, Σ, δ, q₀, F)
B) 6-tuple (Q, Σ, Γ, δ, q₀, F)
C) 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
D) 3-tuple (Q, Γ, δ)

Correct answer: C — 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

Reference: VU handout, Lectures 23–45 — Computability theory: Turing machines. Page — not confirmed in source.

Status: Verified

Q2. The Church–Turing thesis states that:

A) Every problem can be solved by a finite automaton
B) Any function that can be computed by an algorithm can be computed by a Turing machine
C) Every decidable language is regular
D) Turing machines are faster than real computers

Correct answer: B — Any function that can be computed by an algorithm can be computed by a Turing machine

Reference: VU handout, Lectures 23–45 — Computability theory: the Church–Turing thesis. Page — not confirmed in source.

Status: Verified

Q3. A language L is decidable (recursive) if:

A) Some Turing machine accepts L
B) Some Turing machine accepts L and halts on every input
C) Some NFA accepts L
D) L is finite

Correct answer: B — Some Turing machine accepts L and halts on every input

Reference: VU handout, Lectures 23–45 — Computability theory: decidable vs recognizable languages. Page — not confirmed in source.

Status: Verified

Q4. The language A_TM = {⟨M, w⟩ : M is a TM and M accepts w} is:

A) Decidable
B) Recognizable but undecidable
C) Not recognizable
D) Regular

Correct answer: B — Recognizable but undecidable

Reference: VU handout, Lectures 23–45 — Computability theory: undecidability. Page — not confirmed in source.

Status: Verified

Q5. If A ≤m B (A is mapping reducible to B) and B is decidable, then:

A) A is undecidable
B) A is decidable
C) A is not recognizable
D) Nothing can be said about A

Correct answer: B — A is decidable

Reference: VU handout, Lectures 23–45 — Computability theory: reducibility. Page — not confirmed in source.

Status: Verified

Q6. If a language L and its complement are both Turing-recognizable, then L is:

A) Not recognizable
B) Decidable
C) Regular
D) Context-free

Correct answer: B — Decidable

Reference: VU handout, Lectures 23–45 — Computability theory: decidability. Page — not confirmed in source.

Status: Verified

Q7. Which of the following inclusions is true?

A) NP ⊆ P
B) P ⊆ NP
C) PSPACE ⊆ P
D) NP ⊆ regular languages

Correct answer: B — P ⊆ NP

Reference: VU handout, Lectures 23–45 — Complexity theory: time complexity, classes P and NP. Page — not confirmed in source.

Status: Verified

Q8. The Boolean satisfiability problem SAT is:

A) In P
B) NP-complete (Cook–Levin theorem)
C) Decidable but not in NP
D) Undecidable

Correct answer: B — NP-complete (Cook–Levin theorem)

Reference: VU handout, Lectures 23–45 — Complexity theory: NP-completeness. Page — not confirmed in source.

Status: Verified

Q9. A problem is NP-complete if it is:

A) In NP and every problem in NP reduces to it in polynomial time (NP-hard and in NP)
B) In P and hard to solve
C) Undecidable
D) Solvable in exponential time only

Correct answer: A — In NP and every problem in NP reduces to it in polynomial time (NP-hard and in NP)

Reference: VU handout, Lectures 23–45 — Complexity theory: NP-completeness. Page — not confirmed in source.

Status: Verified

Q10. Which chain of inclusions is correct?

A) P ⊆ NP ⊆ PSPACE
B) NP ⊆ P ⊆ PSPACE
C) PSPACE ⊆ NP ⊆ P
D) P ⊆ PSPACE ⊆ NP

Correct answer: A — P ⊆ NP ⊆ PSPACE

Reference: VU handout, Lectures 23–45 — Complexity theory: time and space complexity. Page — not confirmed in source.

Status: Verified

3. Midterm Subjective

Q1. Define a DFA formally and construct a DFA that accepts all strings over {0, 1} ending in "01".

Answer: A DFA is a 5-tuple (Q, Σ, δ, q₀, F), where Q is a finite set of states, Σ is the alphabet, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accept states. For strings ending in "01" over {0, 1}: use states q₀ (no useful suffix seen), q₁ (last symbol seen was 0), q₂ (last two symbols were 01 — accept). Transitions: δ(q₀, 0) = q₁, δ(q₀, 1) = q₀, δ(q₁, 0) = q₁, δ(q₁, 1) = q₂, δ(q₂, 0) = q₁, δ(q₂, 1) = q₀. Start state q₀, accept state F = {q₂}. Check: "101" ends in 01 → q₀→q₀→q₁→q₂, accepted; "010" → q₀→q₁→q₂→q₁, rejected.

Reference: VU handout, Lectures 1–22 — Automata theory: finite automata. Page — not confirmed in source.

Status: Verified

Q2. Convert the NFA below to an equivalent DFA by subset construction. NFA: states {q₀, q₁}, start q₀, accept {q₁}; transitions: δ(q₀, 0) = {q₀, q₁}, δ(q₀, 1) = {q₁}, δ(q₁, 0) = ∅, δ(q₁, 1) = {q₀, q₁}.

Answer: Subset construction: DFA states are subsets of {q₀, q₁}. Start state {q₀}. δ'({q₀}, 0) = {q₀, q₁}; δ'({q₀}, 1) = {q₁}. δ'({q₀, q₁}, 0) = δ(q₀, 0) ∪ δ(q₁, 0) = {q₀, q₁}; δ'({q₀, q₁}, 1) = δ(q₀, 1) ∪ δ(q₁, 1) = {q₁} ∪ {q₀, q₁} = {q₀, q₁}. δ'({q₁}, 0) = ∅; δ'({q₁}, 1) = {q₀, q₁}. Accept states are subsets containing q₁: {q₁} and {q₀, q₁}. The DFA has states {q₀}, {q₁}, {q₀, q₁} (and the dead state ∅). It accepts exactly the strings the NFA accepts — for example "0" goes {q₀} → {q₀, q₁}, which is accepting.

Reference: VU handout, Lectures 1–22 — Automata theory: NFA to DFA conversion. Page — not confirmed in source.

Status: Verified

Q3. Prove that the language L = {a^n b^n : n ≥ 0} is not regular, using the pumping lemma for regular languages.

Answer: Suppose, for contradiction, that L is regular, and let p be its pumping length. Take w = a^p b^p, which is in L and |w| = 2p ≥ p. By the pumping lemma, w = xyz with |xy| ≤ p, |y| > 0, and xyⁱz ∈ L for all i ≥ 0. Since |xy| ≤ p, the part xy lies entirely within the a's, so y = a^k for some k > 0. Pumping down (i = 0) gives xz = a^(p−k) b^p, which has fewer a's than b's and is therefore not in L — a contradiction. Hence no such p exists and L is not regular.

Reference: VU handout, Lectures 1–22 — Automata theory: pumping lemma for regular languages. Page — not confirmed in source.

Status: Verified

Q4. Give a context-free grammar for the language {a^n b^n : n ≥ 0} and derive the string "aabb".

Answer: Grammar G with S → aSb | ε. Derivation of "aabb": S ⇒ aSb (apply S → aSb) ⇒ aaSbb (apply S → aSb again) ⇒ aabb (apply S → ε). The grammar generates exactly {a^n b^n}: each use of S → aSb adds one a on the left and one b on the right, keeping the counts equal, and S → ε stops the derivation. So the language is context-free, even though (by Q3) it is not regular.

Reference: VU handout, Lectures 1–22 — Context-free grammars. Page — not confirmed in source.

Status: Verified

Q5. Show that the language of strings over {0, 1} with an even number of 0s is regular, by giving a DFA for it.

Answer: Use two states: q_even (seen an even number of 0s so far — start and accept state) and q_odd (seen an odd number of 0s). Transitions: δ(q_even, 0) = q_odd, δ(q_even, 1) = q_even, δ(q_odd, 0) = q_even, δ(q_odd, 1) = q_odd. Every 0 flips the parity, every 1 leaves it unchanged, so after reading a string the machine is in q_even exactly when the string has an even number of 0s. Since a DFA accepts it, the language is regular. (Equivalently, its regular expression is 1* (0 1* 0 1*)*.)

Reference: VU handout, Lectures 1–22 — Automata theory: finite automata; regular languages. Page — not confirmed in source.

Status: Verified

4. Finalterm Subjective

Q1. Define a Turing machine formally (7-tuple) and explain how it differs from a finite automaton.

Answer: A Turing machine is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject), where Q is a finite set of states, Σ is the input alphabet (not containing the blank ␣), Γ is the tape alphabet (Σ ⊆ Γ, and ␣ ∈ Γ), δ: Q × Γ → Q × Γ × {L, R} is the transition function, q₀ is the start state, and q_accept, q_reject are the accept and reject states. Differences from an FA: (i) a TM has an infinite tape it can read and write, so it has unbounded memory, while an FA has only its finite state; (ii) a TM's head moves left and right, while an FA reads its input once, left to right; (iii) a TM can loop forever without halting, while an FA always halts after reading the input; (iv) a TM can both accept and reject, and may not halt at all. That is why TMs decide languages FAs cannot, such as {a^n b^n c^n}.

Reference: VU handout, Lectures 23–45 — Computability theory: Turing machines. Page — not confirmed in source.

Status: Verified

Q2. State the Church–Turing thesis and explain what it claims.

Answer: The Church–Turing thesis states that the informal, intuitive notion of an algorithm is exactly captured by a Turing machine: any function that can be computed by an algorithm (by any reasonable, mechanical procedure) can be computed by some Turing machine. It is a thesis, not a theorem, because "algorithm" is an informal concept that cannot be proved equal to a formal one. Its evidence is that every other proposed model of computation — lambda calculus, recursive functions, Post systems, real programming languages — has turned out to be equivalent in power to Turing machines. The thesis is what lets us use Turing machines to reason about what computers can and cannot do in principle.

Reference: VU handout, Lectures 23–45 — Computability theory: the Church–Turing thesis. Page — not confirmed in source.

Status: Verified

Q3. Prove that the Halting Problem is undecidable (diagonalization sketch).

Answer: Suppose, for contradiction, that a TM H decides the halting problem: H(⟨M, w⟩) accepts if M halts on w and rejects if M loops on w. Build a TM D that on input ⟨M⟩ runs H on ⟨M, ⟨M⟩⟩ (i.e. asks whether M halts on its own description); if H accepts, D loops forever; if H rejects, D halts. Now run D on its own description ⟨D⟩: if D halts on ⟨D⟩, then H(⟨D, ⟨D⟩⟩) accepts, so D loops — contradiction; if D loops on ⟨D⟩, then H rejects, so D halts — contradiction. Both cases are impossible, so H cannot exist. Hence no Turing machine decides whether an arbitrary TM halts on an arbitrary input: the Halting Problem is undecidable.

Reference: VU handout, Lectures 23–45 — Computability theory: undecidability. Page — not confirmed in source.

Status: Verified

Q4. Define the complexity classes P and NP. Is it known whether P = NP?

Answer: P is the class of languages decidable in polynomial time by a deterministic single-tape Turing machine: L ∈ P if some deterministic TM decides L in O(n^k) steps for some constant k. NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine — equivalently, the languages that have polynomial-time verifiers (a proposed solution can be checked in polynomial time). Clearly P ⊆ NP, because a deterministic polynomial-time decider is also a nondeterministic one. Whether P = NP — whether every problem whose solution can be verified quickly can also be solved quickly — is NOT known; it is the most famous open problem in computer science, with a $1,000,000 Clay Millennium Prize. Most researchers believe P ≠ NP, but no proof exists either way.

Reference: VU handout, Lectures 23–45 — Complexity theory: time complexity; classes P and NP. Page — not confirmed in source.

Status: Verified

Q5. What is a polynomial-time reduction, and what is the significance of SAT being NP-complete?

Answer: A polynomial-time (mapping) reduction from A to B, written A ≤p B, is a polynomial-time computable function f such that w ∈ A if and only if f(w) ∈ B. It means A is "no harder than" B: if B can be solved in polynomial time, so can A (solve f(w) instead); and if A is hard, B is at least as hard. A language is NP-complete if it is in NP and every NP language reduces to it in polynomial time. The Cook–Levin theorem says SAT (Boolean satisfiability) is NP-complete — it was the first problem proved NP-complete. Its significance: once SAT is known NP-complete, any other NP problem can be shown NP-complete by reducing SAT (or another NP-complete problem) to it, so hundreds of practical problems (3-SAT, vertex cover, Hamiltonian path, travelling salesperson, etc.) are now known to be NP-complete; a polynomial-time algorithm for any one of them would give one for all of them.

Reference: VU handout, Lectures 23–45 — Complexity theory: NP-completeness. Page — not confirmed in source.

Status: Verified