COS3701 Assignment 3 2026 |Theoretical Computer
Science III | 2026 EXAM with Questions and
Answers/Plus a Rationale Updated 2026 A+/Instant
Download PDF
EXAM COVERAGE
1. Automata and Formal Languages: Regular and Context-Free Grammars
2. Pushdown Automata and Turing Machines
3. Computability Theory and Decidability
4. Complexity Theory: P, NP, and NP-Completeness
1. Let G be a context-free grammar with productions generating strings over the alphabet {0, 1}.
When converting G into Chomsky Normal Form (CNF), which type of production rule must be
systematically eliminated first before addressing unit and useless productions?
A. Unit productions of the form A -> B
B. Epsilon-productions and nullable variables
C. Productions with more than two non-terminals on the right-hand side
D. Terminal-containing mixed productions of the form A -> aB
CORRECT ANSWER : B
Rationale: The standard algorithmic conversion to Chomsky Normal Form requires eliminating
epsilon-productions first, followed by unit productions, and finally rules containing mixed
terminals or long right-hand sides. Option A represents the second elimination step. Options C
and D address length and mixed rules handled in subsequent steps.
2. Consider the language L = {a^n b^n c^n | n >= 1}. Why does the standard pumping lemma for
regular languages fail to prove that L is non-regular, whereas Ogden's lemma or context-free
pumping lemma can be successfully applied?
A. Because regular languages cannot recognize any counting mechanism
, B. Because regular languages cannot correlate counts of three distinct symbols
simultaneously due to finite state memory limitations
C. Because L is actually a regular language accepted by a deterministic finite automaton with an
infinite state set
D. Because the pumping length constraint is violated by the alphabet size
CORRECT ANSWER : B
Rationale: Finite automata have fixed, finite memory states and cannot track or compare three
independent quantities (n for a, b, and c) simultaneously. Option A is false because some limited
counting is possible. Option C and D misstate automata properties.
3. In the context of Turing machine variants, a multi-tape Turing machine is proven to be
computationally equivalent in power to a single-tape Turing machine. What is the precise time
complexity overhead incurred when simulating a k-tape Turing machine with a single-tape
Turing machine?
A. Linear time overhead O(n)
B. Quadratic time overhead O(n^2)
C. Exponential time overhead O(2^n)
D. Logarithmic time overhead O(n log n)
CORRECT ANSWER : B
Rationale: Simulating k tapes on a single tape requires the single head to scan back and forth
across different track markers to represent each tape, resulting in a quadratic slowdown where
time T(n) becomes O(T(n)^2). Options A, C, and D underestimate or overestimate the actual
simulation complexity.
4. Which of the following decision problems concerning context-free grammars (CFGs) is known
to be undecidable?
A. Determining whether a given string is generated by a specific CFG
B. Determining whether two given CFGs generate the same language (L(G1) = L(G2))
C. Determining whether the language generated by a CFG is empty
D. Determining whether a CFG generates any strings of length less than ten
CORRECT ANSWER : B
, Language equivalence for general context-free grammars is undecidable, meaning no general
algorithm can solve it for all CFGs. Options A, C, and D are decidable properties for context-
free grammars using standard parsing and graph reachability algorithms.
5. When applying the Myhill-Nerode theorem to prove that a language L over {0, 1} is non-regular,
what must one establish regarding the equivalence classes of the indistinguishability relation
R_L?
A. The number of equivalence classes must be finite and bounded by the string length
B. The index of R_L (the number of equivalence classes) must be infinite
C. Every equivalence class must contain an infinite number of palindromes
D. The relation must be symmetric and transitive but fail reflexivity
CORRECT ANSWER : B
Rationale: According to the Myhill-Nerode theorem, a language L is regular if and only if the
equivalence relation R_L has a finite index (a finite number of equivalence classes). Proving an
infinite index demonstrates non-regularity. Options A, C, and D distort the theorem's core
criteria.
6. Which complexity class captures the set of decision problems solvable by a deterministic Turing
machine in polynomial time with respect to the input length?
A. NP
B. P
C. EXPTIME
D. PSPACE
CORRECT ANSWER : B
Rationale: The class P (Polynomial time) consists of all decision problems solvable by a
deterministic Turing machine within a time complexity bounded by a polynomial function of the
input size. Options A, C, and D represent larger or non-deterministic classes.
7. In structural complexity theory, a language B is polynomial-time many-one reducible (or Karp
reducible) to a language A, denoted B <=_p A, if there exists a polynomial-time computable
function f such that for all x, x in B if and only if:
A. f(x) in B
, B. f(x) in A
C. x not in A
D. f(x) not in B
CORRECT ANSWER : B
Rationale: Karp reduction requires a polynomial-time computable function f mapping instances
of B to instances of A such that membership is preserved: x is in B if and only if f(x) is in A.
Options A, C, and D fail to correctly define mapping reduction membership equivalence.
8. Which of the following problems is universally recognized as NP-complete, serving as the
foundational cornerstone for Cook-Levin theorem proofs?
A. The Halting Problem (A_TM)
B. The Boolean Satisfiability Problem (SAT)
C. The Traveling Salesperson Problem on trees
D. The Primality Testing Problem
CORRECT ANSWER : B
Rationale: Stephen Cook proved that SAT is NP-complete, establishing it as the benchmark
problem to which other NP problems can be reduced. Option A is undecidable, not NP-complete.
Option C on trees is solvable in polynomial time. Option D is in P.
9. What is the primary operational distinction between a Deterministic Pushdown Automaton
(DPDA) and a Non-deterministic Pushdown Automaton (NPDA)?
A. DPDAs can utilize an infinite stack, whereas NPDAs are restricted to a finite stack height
B. DPDAs cannot tolerate ambiguous transitions, epsilon-transition conflicts, or multiple
valid choices for a single configuration
C. DPDAs accept context-sensitive languages, while NPDAs accept regular languages
D. DPDAs operate without a stack, functioning identical to deterministic finite automata
CORRECT ANSWER : B
Rationale: Deterministic pushdown automata are strictly constrained to have at most one valid
move for any configuration (no conflicting symbol reads, state jumps, or epsilon vs. terminal
Science III | 2026 EXAM with Questions and
Answers/Plus a Rationale Updated 2026 A+/Instant
Download PDF
EXAM COVERAGE
1. Automata and Formal Languages: Regular and Context-Free Grammars
2. Pushdown Automata and Turing Machines
3. Computability Theory and Decidability
4. Complexity Theory: P, NP, and NP-Completeness
1. Let G be a context-free grammar with productions generating strings over the alphabet {0, 1}.
When converting G into Chomsky Normal Form (CNF), which type of production rule must be
systematically eliminated first before addressing unit and useless productions?
A. Unit productions of the form A -> B
B. Epsilon-productions and nullable variables
C. Productions with more than two non-terminals on the right-hand side
D. Terminal-containing mixed productions of the form A -> aB
CORRECT ANSWER : B
Rationale: The standard algorithmic conversion to Chomsky Normal Form requires eliminating
epsilon-productions first, followed by unit productions, and finally rules containing mixed
terminals or long right-hand sides. Option A represents the second elimination step. Options C
and D address length and mixed rules handled in subsequent steps.
2. Consider the language L = {a^n b^n c^n | n >= 1}. Why does the standard pumping lemma for
regular languages fail to prove that L is non-regular, whereas Ogden's lemma or context-free
pumping lemma can be successfully applied?
A. Because regular languages cannot recognize any counting mechanism
, B. Because regular languages cannot correlate counts of three distinct symbols
simultaneously due to finite state memory limitations
C. Because L is actually a regular language accepted by a deterministic finite automaton with an
infinite state set
D. Because the pumping length constraint is violated by the alphabet size
CORRECT ANSWER : B
Rationale: Finite automata have fixed, finite memory states and cannot track or compare three
independent quantities (n for a, b, and c) simultaneously. Option A is false because some limited
counting is possible. Option C and D misstate automata properties.
3. In the context of Turing machine variants, a multi-tape Turing machine is proven to be
computationally equivalent in power to a single-tape Turing machine. What is the precise time
complexity overhead incurred when simulating a k-tape Turing machine with a single-tape
Turing machine?
A. Linear time overhead O(n)
B. Quadratic time overhead O(n^2)
C. Exponential time overhead O(2^n)
D. Logarithmic time overhead O(n log n)
CORRECT ANSWER : B
Rationale: Simulating k tapes on a single tape requires the single head to scan back and forth
across different track markers to represent each tape, resulting in a quadratic slowdown where
time T(n) becomes O(T(n)^2). Options A, C, and D underestimate or overestimate the actual
simulation complexity.
4. Which of the following decision problems concerning context-free grammars (CFGs) is known
to be undecidable?
A. Determining whether a given string is generated by a specific CFG
B. Determining whether two given CFGs generate the same language (L(G1) = L(G2))
C. Determining whether the language generated by a CFG is empty
D. Determining whether a CFG generates any strings of length less than ten
CORRECT ANSWER : B
, Language equivalence for general context-free grammars is undecidable, meaning no general
algorithm can solve it for all CFGs. Options A, C, and D are decidable properties for context-
free grammars using standard parsing and graph reachability algorithms.
5. When applying the Myhill-Nerode theorem to prove that a language L over {0, 1} is non-regular,
what must one establish regarding the equivalence classes of the indistinguishability relation
R_L?
A. The number of equivalence classes must be finite and bounded by the string length
B. The index of R_L (the number of equivalence classes) must be infinite
C. Every equivalence class must contain an infinite number of palindromes
D. The relation must be symmetric and transitive but fail reflexivity
CORRECT ANSWER : B
Rationale: According to the Myhill-Nerode theorem, a language L is regular if and only if the
equivalence relation R_L has a finite index (a finite number of equivalence classes). Proving an
infinite index demonstrates non-regularity. Options A, C, and D distort the theorem's core
criteria.
6. Which complexity class captures the set of decision problems solvable by a deterministic Turing
machine in polynomial time with respect to the input length?
A. NP
B. P
C. EXPTIME
D. PSPACE
CORRECT ANSWER : B
Rationale: The class P (Polynomial time) consists of all decision problems solvable by a
deterministic Turing machine within a time complexity bounded by a polynomial function of the
input size. Options A, C, and D represent larger or non-deterministic classes.
7. In structural complexity theory, a language B is polynomial-time many-one reducible (or Karp
reducible) to a language A, denoted B <=_p A, if there exists a polynomial-time computable
function f such that for all x, x in B if and only if:
A. f(x) in B
, B. f(x) in A
C. x not in A
D. f(x) not in B
CORRECT ANSWER : B
Rationale: Karp reduction requires a polynomial-time computable function f mapping instances
of B to instances of A such that membership is preserved: x is in B if and only if f(x) is in A.
Options A, C, and D fail to correctly define mapping reduction membership equivalence.
8. Which of the following problems is universally recognized as NP-complete, serving as the
foundational cornerstone for Cook-Levin theorem proofs?
A. The Halting Problem (A_TM)
B. The Boolean Satisfiability Problem (SAT)
C. The Traveling Salesperson Problem on trees
D. The Primality Testing Problem
CORRECT ANSWER : B
Rationale: Stephen Cook proved that SAT is NP-complete, establishing it as the benchmark
problem to which other NP problems can be reduced. Option A is undecidable, not NP-complete.
Option C on trees is solvable in polynomial time. Option D is in P.
9. What is the primary operational distinction between a Deterministic Pushdown Automaton
(DPDA) and a Non-deterministic Pushdown Automaton (NPDA)?
A. DPDAs can utilize an infinite stack, whereas NPDAs are restricted to a finite stack height
B. DPDAs cannot tolerate ambiguous transitions, epsilon-transition conflicts, or multiple
valid choices for a single configuration
C. DPDAs accept context-sensitive languages, while NPDAs accept regular languages
D. DPDAs operate without a stack, functioning identical to deterministic finite automata
CORRECT ANSWER : B
Rationale: Deterministic pushdown automata are strictly constrained to have at most one valid
move for any configuration (no conflicting symbol reads, state jumps, or epsilon vs. terminal
