2K6CS 503: THEORETICAL FOUNDATION OF COMPUTATION / IT 503 THEORY OF AUTOMATA & FORMAL LANGUAGES
Module I (14 hours)
Introduction; alphabets, Strings and Languages; Automata and Grammars -Finite automata (FA) -DFA-NFA – Finite Automata with epsilon-transitions-Equivalence of DFAs and NFAs -Regular expressions (RE) -Definition, RE to FA, FA to RE, algebraic laws for RE, applications of REs. -Regular grammars and FA -Proving languages to be non-regular -Pumping Lenma – Applications. Closure properties of Regular languages -Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc. –Myhill-Nerode theorem-DFA Minimization – Decision properties of Regular languages – Two-way finite automata, Finite automata with output.
Module II (13 hours)
Context-free Grammars (CFG) -Parse tree – Ambiguity in grammars and Languages-Applications of CFGPushdown Automata (PDA) -Equivalence of PDAs and CFGs -DPDAs -Definition, DPDAs and Regular Languages,-DPDA and Ambiguous grammars–CYK algorithm -Simplification of CFGs -Normal forms -CNF and GNF –Pumping lemma for CFLs,Closure properties of CFLs – Decision properties of CFL.
Module III (13 hours)
Turing Machines -Formal definition and behavior – TM as a computer of integer functions -Programming techniques for TMs -Storage in state, multiple tracks, subroutines, etc.-Computing a partial function with Turing machineVariants of TMs –Multitape TMs, Nondeterministic TMs. -TMs with semi-infinite tapes, multistack machines.- universal Turing Machines-Equivalence of the various variants with the basic model- Models of computation and Church-Turing Thesis.
Module IV (13 hours)
Computability – Closure properties of recursive and recursively enumerable language. Undecidability- A language that is not RE – An undecidable problem that is RE – Undecidable problems about TM-Halting problem – Post Correspondence Problem – The Chomsky hierarchy – Context sensitive language and LBA –Equivalence of LBA and CSG.
Text books
1. J E Hopcroft And J D Ullman : Introduction to Automata Theory and Computation, Addison Wesley
2. John C Martin : Introduction to Languages and the Theory of Computation(3 rd Edition) , TMH
Reference books
1. H R Lewis and C H Papadimitriou : Elemnts of Theory of Computation
2. Sipser : Introduction to theory of Computation, CENAGE LEARNING Indian Edition
3. Linz P : An Introduction to Formal Languages and Automata, Narosa