Automata Theory And Computability
Semester : V
Course Code : 18CS54
CIE Marks : 40 SEE Marks : 60
AUTOMATA THEORY AND COMPUTABILITY
18CS54
SYLLABUS
Module-1
Why study 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
Module-2
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
Module-3
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, Non-determinism 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
Module-4
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
Module-5
Decidability: Definition of an algorithm, decidability, decidable languages, Undecidable languages, the halting problem of TM, Post correspondence problem. Complexity: Growth rate 08 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