Module-4 (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 – 4 Contact
Algorithms and Decision Procedures for CFLs: Decidable questions, Un-decidable
questions. Turing Machine: Turing machine model, Representation, Language acceptability
by TM, design of TM, Techniques for TM construction. Variants of Turing Machines (TM),
The model of Linear Bounded automata.
Textbook 1: Ch 14: 14.1, 14.2, Textbook 2: Ch 9.1 to 9.8