Introduction: Finite state automata, Non-deterministic finite state automata, FA with-transitions, Regular expressions, FA with outputs, Applications of FA. Properties of regular sets-Pumping Lemma, Closure properties, Myhill-Nerode Theorem, Minimization of FA, Decision Algorithms.



Context Free Grammars and Languages:Derivations, Parse-trees, Ambiguity in Grammars and Languages. Pushdown Automata–Definitions, The languages of PDA, Equivalence of PDAs and CFGs, Deterministic Pushdown Automata (DPDA).



Properties of CFLs:Normal forms for CFGs, Pumping Lemma, Closure properties, Decision algorithms, Deterministic Context Free Languages, Predicting machines, Decision properties, LR(0) grammars, LR(0) and DPDA,LR(k) grammars



Turing Machines:Introduction, Computational Languages and Functions, Techniques for construction of Turing machines. Modifications of TM, TM as enumerator, Restricted TM.



Undecidability: Recursive and Recursively enumerable languages, UTM and undecidable problem, Rice Theorem, Post’s correspondence problem. Chomsky’s Hierarchy–Regular grammars, Unrestricted grammar, CSL, Relationship between classes of languages.

Previous year question papers​

Youtube lectures

Unit 1 Playlist

Unit 2&3 Playlist

Unit 4 Playlist

Unit 5 Playlist