Theory of Computation

Construct a context-free grammar for a specified language and prove its correctness by structural induction.

Demonstrate that a context-free grammar is ambiguous by producing two distinct parse trees or leftmost derivations for one string.

Prove that a language is not context-free using the pumping lemma for context-free languages.

Prove that a language is not context-free by intersecting it with a regular language and applying closure properties.

Prove that a language is decidable by specifying a halting Turing-machine algorithm and establishing its termination and correctness.

Construct a mapping reduction by defining a computable transformation and proving the required if-and-only-if condition.

Prove a language undecidable by reducing from the acceptance problem for Turing machines.

Prove that a language is not Turing-recognizable using complement closure and a known recognizable-but-undecidable language.

Apply Rice’s theorem after verifying that a property of Turing-machine languages is semantic and nontrivial.

Prove that a decision problem belongs to P by giving an algorithm and bounding its running time polynomially.

Prove that a decision problem belongs to NP by defining a polynomial-size certificate and polynomial-time verifier.

Prove a polynomial-time many-one reduction correct by establishing both its logical equivalence and time bound.

Prove a decision problem NP-complete by combining NP membership with a reduction from a known NP-complete problem.

Identify and repair reversed directions, incomplete equivalences, and invalid runtime claims in reduction proofs.