Module-1(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 – 1 Contact
Why study the Theory of Computation, Languages and Strings: Strings, Languages. A
Language Hierarchy, Computation, Finite State Machines (FSM): Deterministic FSM,
Regular languages, Designing FSM, Nondeterministic FSMs, From FSMs to Operational
Systems, Simulators for FSMs, Minimizing FSMs, Canonical form of Regular languages,
Finite State Transducers, Bidirectional Transducers.
Textbook 1: Ch 1,2, 3,4, 5.1 to 5.10