CS3452 Theory of Computation Previous Year Question Papers - Anna University

UNIT I: Automata and Regular Expressions

Part A (2 Marks)

• Define Deterministic Finite Automata (DFA).
• What is the difference between NFA and DFA?
• Write a regular expression for a set of strings starting with 'a' and ending with 'b'.
• Define ε-closure of a state.
• State the Pumping Lemma for regular languages.

Part B (13 Marks)

• Explain the procedure to convert NFA to DFA with a suitable example.
• Discuss the conversion of ε-NFA to DFA.
• Explain the Equivalence of Finite Automata and Regular Expressions (Arden's Theorem or State Elimination Method).
• Describe the Minimization of DFA using the Table Filling algorithm.

UNIT II: Context-Free Grammars and Languages

Part A (2 Marks)

• Define Context-Free Grammar (CFG).
• What is an Ambiguous Grammar? Give an example.
• Define Derivation Tree (Parse Tree).
• Distinguish between Leftmost and Rightmost Derivation.
• What is Chomsky Normal Form (CNF)?

Part B (13 Marks)

• Explain the simplification of CFG: Removal of Null, Unit, and Useless productions.
• Discuss the conversion of a grammar into Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).
• Explain the Pumping Lemma for Context-Free Languages and use it to prove a language is not CFL.
• Describe the Closure properties of Context-Free Languages.

UNIT III: Pushdown Automata

Part A (2 Marks)

• Define Pushdown Automata (PDA).
• What are the different types of acceptance in PDA (Final state vs. Empty stack)?
• Is the language L = {w c w^R} accepted by a Deterministic PDA?
• What is the difference between DPDA and NPDA?
• Define the formal components of a PDA (7-tuple).

Part B (13 Marks)

• Construct a PDA for a given language (e.g., L = {a^n b^n | n ≥ 1} or L = {ww^R}).
• Explain the conversion of CFG to PDA and PDA to CFG.
• Discuss the Equivalence of PDA acceptance by Empty Stack and Final State.

UNIT IV: Turing Machines

Part A (2 Marks)

• Define a Turing Machine (TM).
• What is a Recursive Enumerable Language?
• What is a Multi-track Turing Machine?
• Define the Halting Problem.
• What is a Universal Turing Machine?

Part B (13 Marks)

• Design a Turing Machine for basic languages (e.g., L = {a^n b^n c^n} or proper subtraction).
• Discuss the different types of Turing Machines (Multi-tape, Non-deterministic, Multi-stack).
• Explain the Chomsky Hierarchy of languages in detail.
• Describe the techniques for Turing Machine construction (Storage in state, Multiple tracks).

UNIT V: Undecidability

Part A (2 Marks)

• When is a problem said to be Decidable?
• Define Post Correspondence Problem (PCP).
• What are P and NP classes?
• Define NP-Complete and NP-Hard problems.
• What is a Reduction in complexity theory?

Part B (13 Marks)

• Explain the Halting Problem of Turing Machine and prove its undecidability.
• Discuss the Post Correspondence Problem (PCP) and its modified version (MPCP).
• Explain the P, NP, NP-Complete, and NP-Hard complexity classes with examples.
• Describe the Decidability of languages and the properties of Recursive and Recursive Enumerable languages.

Most Repeated / High-Weight Questions

NFA to DFA conversion and minimization, CFG to CNF conversion, PDA construction for context-free languages, Turing machine design for specific languages, Chomsky hierarchy, halting problem and undecidability proofs, NP-completeness.