BCSCCS302R03 Theory of Computation

Unit - I
Introduction: Preliminaries and notations-basic concepts-applications. 
Finite Automata: Deterministic FA – non deterministic FA- Equivalence-minimization. 
Regular languages and regular grammars: Relation between regular languages and regular expressions-regular grammars- construction of automata using JFLAP.  
Lex in syntaxical analysis:  Declarations-regular expressions-productions-additional code-examples. 
Properties of Regular Languages:  Closure properties-identifying non regular languages.

Unit - II
Context Free Languages: Context free grammars- parsing and ambiguity-left and right recursions and its removal-top down parsing predictive parsers-bottom up parsing using SLR(1).  
Syntaxical analysis using Yacc: Declaration and additional code-examples. 
Simplification and Normal Forms:  Transformations – two important normal forms-membership algorithm for CFG.

Unit - III 
Push Down Automata: Non Deterministic PDA-PDA and CFL-Deterministic PDA and determinsitic CFL-Grammars for deterministic CFL.
Properties of CFL: Closure properties and decision algorithm for CFL.   
Turing Machines: Standard TM-TM for complicated tasks-Turing thesis. 
Other models of TM: Minor variations on TM-TM with complex storage-non deterministic TM- Universal TM-linear bounded automata-construction of PDA and TM using JFLAP.

Unit - IV  A hierarchy of formal languages and automata: Recursive and recursive enumerable languages- unrestricted grammars-context sensitive grammars and languages-Chomsky Hierarchy.  
Limits of algorithm computation:  
unsolvable problems by TM-Undecidable problems for recursively enumerable languages-post correspondence problem-undecidable problems for CFL.  
Other models of computation: Recursive functions-post systems-rewriting systems. 
An overview of computational complexity.
Text Books:
1. Peter Linz, “An Introduction to Formal Languages and Automata”, 5th Edition, Jones and Bartlet Learning International, United Kingdom, 2011.
2. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, “Compilers Principles, Techniques, & Tools”, Pearson Education, 2007.
3. John R. Levine, Tony Mason, Doug Brown, “ Lex and Yacc”, Oreilly Media, 1992.
1. John E. Hopcroft,  Rajeev Motwani, Jeffery D Ullman, “ Introduction to Automata Theory, Languages and Computation”, 3rd Edition, Pearson Education, 2007.
2. Susan H. Rodger and Thomas W. Finley, “JFLAP: An Interactive Formal Languages and Automata Package “,  Jones & Bartlett Publishers, Sudbury, MA, 2006.
3. Michael Sipser, “Introduction to the theory of computation”, 2nd Edition, Thomson Course Technology, 2006.