Subject Code: CS3L001  Name: Formal Languages and Automata Theory L-T-P: 3-1-0 Credit: 4
Pre-requisite(s):  None
Finite Automata: Basic Concepts, Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), Equivalence between NFA and DFA; Regular Languages:Regular expression and equivalence to Finite Automata (FA),  Algebraic laws for regular expressions,  pumping lemma and applications, properties of regular languages, minimization of automata and applications; Context-free languages: Context-free grammars (CFG)and languages, pushdown automaton (PDA), various forms of PDA, equivalence between CFG and PDA, Chmosky normal form of CFG, pumping lemma, properties of CFLs; Turing Machines: Turing machines, decidability and undecidability.
Text Books:
1. Michael Sipser : Introduction to the Theory of Computation, 3rd edition, PWS Publishing
Company,  2012.
2. E. Hopcroft, R. Motwani and J. D. Ullman: Introduction to Automata Theory, Languages and
Computation. Low priced paperback edition, published by Pearson Education, 2007.
Reference Books:
  1. H. R. Lewis and C. H. Papadimitriou. Elements of the Theory of Computation, Eastern economy edition, 1998.