17CS54
AUTOMATA THEORY AND COMPUTABILITY
[As per Choice Based Credit System (CBCS) scheme]
(Effective from the academic year 2017-2018)
SEMESTER - V

This Page Provides Information ABOUT AUTOMATA THEORY AND COMPUTABILITY - ATC Module 1
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

TEXT BOOK MODULE WISE
1. Elaine Rich, Automata, Computability and Complexity, 1st Edition, Pearson Education,2012/2013
2. K L P Mishra, N Chandrasekaran , 3rd Edition, Theory of Computer Science, PhI, 2012