0.0 Introduction to theory of computation

A brief Introduction to CS6503 - THEORY OF COMPUTATION

1. Introduction to THEORY OF COMPUTATION Sampath Kumar S, AP/CSE, SECE

2. THEORY OF COMPUTATION In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm . 6 July 2017 2

3. THEORY OF COMPUTATION Computation: Task performed by ‘calculator’ or ‘computer’ or a ‘machine’. Theory: What is the theory behind about this machine Capabilities of the machine Problems that could be solved by this machine Limitations of thi s machine 6 July 2017 3

4. Branches of ToC The field is divided into three major branches: Automata theory and language Computability theory Computational complexity theory which are linked by the question: "What are the fundamental capabilities and limitations of computers?“. 6 July 2017 4

5. OBJECTIVES of this course: Understand various Computing models like Finite State Machine, Pushdown Automata, and Turing Machine. Be aware of Decidability and Un-decidability of various problems. Learn types of grammars. 6 July 2017 5

6. UNIT I: FINITE AUTOMATA Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite Automaton – DFA & NDFA – Finite Automaton with €- moves – Regular Languages - Regular Expression – Equivalence of NFA and DFA – Equivalence of NDFA’s with and without €-moves – Equivalence of finite Automaton and regular expressions –Minimization of DFA - Pumping Lemma for Regular sets – Problems based on Pumping Lemma. 6 July 2017 6

7. UNIT II: GRAMMARS Grammar Introduction – Types of Grammar - Context Free Grammars and Languages – Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees – Simplification of CFG – Elimination of Useless symbols - Unit productions - Null productions – Greiback Normal form – Chomsky normal form – Problems related to CNF and GNF. 6 July 2017 7

8. UNIT III: PUSHDOWN AUTOMATA Pushdown Automata - Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL - pumping lemma for CFL – problems based on pumping Lemma. 6 July 2017 8

9. UNIT IV: TURING MACHINES Definitions of Turing machines – Models – Computable languages and functions –Techniques for Turing machine construction – Multi head and Multi tape Turing Machines - The Halting problem – Partial Solvability – Problems about Turing machine- Chomskian hierarchy of languages. 6 July 2017 9

10. UNIT V: UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS Unsolvable Problems and Computable Functions – Primitive recursive functions – Recursive and recursively enumerable languages – Universal Turing machine. MEASURING AND CLASSIFYING COMPLEXITY: Tractable and Intractable problems- Tractable and possibly intractable problems – P and NP completeness - Polynomial time reductions. 6 July 2017 10

11. OUTCOMES: Design Finite State Machine, Pushdown Automata, and Turing Machine. Explain the Decidability or Undecidability of various problems 6 July 2017 11

12. Applications of ToC Artificial Intelligence Compiler Design Robotics Circuit Design Natural Language Processing Knowledge based System Quantum Computing Pattern Recognition 6 July 2017 12

13. 6 July 2017 13

14. நன்றி  6 July 2017 14