AUTOMATA THEORY AND COMPUTABILITY VTU Module 5 (18CS54) Notes 5th Semester pdf, Module-5 (18CS54) AUTOMATA THEORY AND COMPUTABILITY VTU Notes Pdf Download
| AUTOMATA THEORY AND COMPUTABILITY (Effective from the academic year 2018 -2019) SEMESTER – V |
||||
| Course Code | 18CS54 | CIE Marks | 40 | |
| Number of Contact Hours/Week | 2:2:0 | SEE Marks | 60 | |
| Total Number of Contact Hours | 40 | Exam Hours | 03 | |
Course Learning Objectives: This course (18CS54) will enable students to:
Introduce core concepts in Automata and Theory of Computation
Identify different Formal language Classes and their Relationships
Design Grammars and Recognizers for different formal languages
Prove or disprove theorems in automata theory using their properties
Determine the decidability and intractability of Computational problems
Module – 5 Contact
Decidability: Definition of an algorithm, decidability, decidable languages, Undecidable
languages, halting problem of TM, Post correspondence problem. Complexity: Growth rate
of functions, the classes of P and NP, Quantum Computation: quantum computers, ChurchTuring thesis. Applications: G.1 Defining syntax of programming language, Appendix J:
Security
Textbook 2: 10.1 to 10.7, 12.1, 12.2, 12.8, 12.8.1, 12.8.2