Theory of Computation
Open in the Padhaiko appPast exam questions (63 with solutions)
Syllabus and lessons
Chapter 1: Introduction to Formal Language, Logic and Proof
- Sets, Functions & Relations
- Propositional Logic, Rules of Inference & Predicate Logic
- Induction, Diagonalization & Pigeonhole Principle
- Alphabets, Languages & Operations on Languages
Chapter 2: Finite Automata and Regular Language
- Finite State Machines & DFA Design
- NFA, ε-NFA & Their Equivalence with DFA
- Regular Expressions & Equivalence with Finite Automata
- Closure Properties, Pumping Lemma & Decision Algorithms
Chapter 3: Context Free Grammar and Pushdown Automata
- CFG, Derivations, Parse Trees & Ambiguity
- Simplification of CFG; CNF, GNF & BNF
- CFL Closure, Pumping Lemma & Decision Algorithms
- Pushdown Automata, CFG↔PDA & Context-Sensitive Grammar
Chapter 4: Turing Machine
- Turing Machines: Representation, Moves & Computing
- TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions