Past exam questions: Theory of Computation
63 questions from past papers, each with a worked solution.
Open in the Padhaiko app2082 Chaitra (Regular)
- Question 1(a) (2 marks): Sets, Functions & Relations
- Question 1(b) (2 marks): Induction, Diagonalization & Pigeonhole Principle
- Question 2 (2 marks): Regular Expressions & Equivalence with Finite Automata
- Question 3 (3 marks): Propositional Logic, Rules of Inference & Predicate Logic
- Question 4 (4 marks): Finite State Machines & DFA Design
- Question 5(a) (3 marks): Closure Properties, Pumping Lemma & Decision Algorithms
- Question 5(b) (3 marks): NFA, ε-NFA & Their Equivalence with DFA
- Question 6 (3 marks): Closure Properties, Pumping Lemma & Decision Algorithms
- Question 7 (4 marks): CFG, Derivations, Parse Trees & Ambiguity
- Question 8 (5 marks): Pushdown Automata, CFG↔PDA & Context-Sensitive Grammar
- Question 9 (3 marks): CFL Closure, Pumping Lemma & Decision Algorithms
- Question 10(a) (1 marks): Turing Machines: Representation, Moves & Computing
- Question 10(b) (3 marks): Turing Machines: Representation, Moves & Computing
- Question 11 (5 marks): Turing Machines: Representation, Moves & Computing
- Question 12(a) (3 marks): TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
- Question 12(b) (3 marks): Turing Machines: Representation, Moves & Computing
- Question 13 (3 marks): Church–Turing Thesis, Universal TM & the Halting Problem
- Question 14(a) (1 marks): Church–Turing Thesis, Universal TM & the Halting Problem
- Question 14(b) (2 marks): TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
- Question 15 (2 marks): Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing
- Question 16 (3 marks): Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing
2082 Kartik (Back)
- Question 1(a)(i) (2 marks): Sets, Functions & Relations
- Question 1(a)(ii) (2 marks): Propositional Logic, Rules of Inference & Predicate Logic
- Question 1(b)(i) (1 marks): Propositional Logic, Rules of Inference & Predicate Logic
- Question 1(b)(ii) (2 marks): Induction, Diagonalization & Pigeonhole Principle
- Question 1(c) (2 marks): Regular Expressions & Equivalence with Finite Automata
- Question 2(a)(i) (2 marks): Finite State Machines & DFA Design
- Question 2(a)(ii) (3 marks): Regular Expressions & Equivalence with Finite Automata
- Question 2(b)(i) (3 marks): Finite State Machines & DFA Design
- Question 2(b)(ii) (1 marks): Finite State Machines & DFA Design
- Question 2(c) (3 marks): Closure Properties, Pumping Lemma & Decision Algorithms
- Question 3(a) (4 marks): CFL Closure, Pumping Lemma & Decision Algorithms
- Question 3(b) (4 marks): Pushdown Automata, CFG↔PDA & Context-Sensitive Grammar
- Question 3(c)(i) (1 marks): Simplification of CFG; CNF, GNF & BNF
- Question 3(c)(ii) (4 marks): Simplification of CFG; CNF, GNF & BNF
- Question 4(a) (6 marks): Turing Machines: Representation, Moves & Computing
- Question 4(b) (3 marks): Turing Machines: Representation, Moves & Computing
- Question 4(c)(i) (3 marks): TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
- Question 4(c)(ii) (2 marks): TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
- Question 5(a) (3 marks): Time/Space Complexity; P, NP & NP-Complete
- Question 5(b)(i) (1 marks): Church–Turing Thesis, Universal TM & the Halting Problem
- Question 5(b)(ii) (2 marks): TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
- Question 6(a) (3 marks): Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing
- Question 6(b) (3 marks): Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing
2081 Chaitra (Regular)
- Question 1(a)(i) (1 marks): Induction, Diagonalization & Pigeonhole Principle
- Question 1(a)(ii) (3 marks): Induction, Diagonalization & Pigeonhole Principle
- Question 1(b) (3 marks): Propositional Logic, Rules of Inference & Predicate Logic
- Question 1(c) (2 marks): Alphabets, Languages & Operations on Languages
- Question 2(a)(i) (2 marks): Finite State Machines & DFA Design
- Question 2(a)(ii) (3 marks): Finite State Machines & DFA Design
- Question 2(b)(i) (1 marks): Closure Properties, Pumping Lemma & Decision Algorithms
- Question 2(b)(ii) (4 marks): NFA, ε-NFA & Their Equivalence with DFA
- Question 2(c) (3 marks): Closure Properties, Pumping Lemma & Decision Algorithms
- Question 3(a) (4 marks): CFG, Derivations, Parse Trees & Ambiguity
- Question 3(b) (5 marks): Simplification of CFG; CNF, GNF & BNF
- Question 3(c) (4 marks): CFL Closure, Pumping Lemma & Decision Algorithms
- Question 4(a) (6 marks): Turing Machines: Representation, Moves & Computing
- Question 4(b) (4 marks): Turing Machines: Representation, Moves & Computing
- Question 4(c) (4 marks): TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
- Question 5(a) (3 marks): Church–Turing Thesis, Universal TM & the Halting Problem
- Question 5(b) (2 marks): Time/Space Complexity; P, NP & NP-Complete
- Question 6(a) (3 marks): Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing
- Question 6(b) (3 marks): Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing