Skip to content
SmartFigureEdu

Anna University · Regulation 2021

CS 3452 Theory of Computation question papers

CS3452 Theory of Computation previous year question papers from Anna University (Regulation 2021), with the full syllabus. Read online or download the PDF.

Fourth semester · Core · L T P C: 3 0 0 3

Question papers

Syllabus

  1. Unit 1: Automata and Regular Expressions9 hours

    Need for automata theory · Introduction to formal proof · Finite Automata (FA) · Deterministic Finite Automata (DFA) · Non-deterministic Finite Automata (NFA) · Equivalence between NFA and DFA · Finite Automata with Epsilon transitions · Equivalence of NFA and DFA · Equivalence of NFAs with and without ε-moves · Conversion of NFA into DFA · Minimization of DFAs

  2. Unit 2: Regular Expressions and Languages9 hours

    Regular expression · Regular Languages · Equivalence of Finite Automata and regular expressions · Proving languages to be not regular (Pumping Lemma) · Closure properties of regular languages

  3. Unit 3: Context Free Grammar and Push Down Automata9 hours

    Types of Grammar · Chomsky's hierarchy of languages · Context-Free Grammar (CFG) and Languages · Derivations and Parse trees · Ambiguity in grammars and languages · Push Down Automata (PDA): Definition · Moves · Instantaneous descriptions · Languages of pushdown automata · Equivalence of pushdown automata and CFG · CFG to PDA · PDA to CFG · Deterministic Pushdown Automata

  4. Unit 4: Normal Forms and Turing Machines9 hours

    Normal forms for CFG · Simplification of CFG · Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) · Pumping lemma for CFL · Closure properties of Context Free Languages · Turing Machine: Basic model · definition and representation · Instantaneous Description · Language acceptance by TM · TM as Computer of Integer functions · Programming techniques for Turing machines (subroutines)

  5. Unit 5: Undecidability9 hours

    Unsolvable Problems and Computable Functions · PCP · MPCP · Recursive and recursively enumerable languages · Properties · Universal Turing machine · Tractable and Intractable problems · P and NP completeness · Kruskal's algorithm · Travelling Salesman Problem · 3-CNF SAT problems