Module-2 (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 – 2 Contact
Regular Expressions (RE): what is a RE?, Kleene‟s theorem, Applications of REs,
Manipulating and Simplifying REs. Regular Grammars: Definition, Regular Grammars and
Regular languages. Regular Languages (RL) and Non-regular Languages: How many RLs,
To show that a language is regular, Closure properties of RLs, to show some languages are
not RLs.
Textbook 1: Ch 6, 7, 8: 6.1 to 6.4, 7.1, 7.2, 8.1 to 8.4