AUTOMATA THEORY AND COMPUTABILITY VTU Module 3 (18CS54) Notes 5th Semester pdf,Module-3 (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 – 3 Contact
Context-Free Grammars(CFG): Introduction to Rewrite Systems and Grammars, CFGs
and languages, designing CFGs, simplifying CFGs, proving that a Grammar is correct,
Derivation and Parse trees, Ambiguity, Normal Forms. Pushdown Automata (PDA):
Definition of non-deterministic PDA, Deterministic and Non-deterministic PDAs, Nondeterminism and Halting, alternative equivalent definitions of a PDA, alternatives that are not
equivalent to PDA.
Textbook 1: Ch 11, 12: 11.1 to 11.8, 12.1, 12.2, 12,4, 12.5, 12.6