| Units | Syllabus |
|---|---|
Unit 1 |
Overview: Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-Transition, Equivalence of NFA’s with and without ε-Transition, Finite Automata with output- Moore Machine, Mealy Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite Automata, Myhill-Nerode Theorem, Simulation of DFA and NFA, Regular expression and Kleen‘s Theorem(with proof), Closure properties of Regular Languages, Pumping Lemma for regular Languages (with proof). |
Unit 2 |
Context Free Grammar(CFG)-Definition, Derivations, Languages, Ambiguity, Regular Grammars-Right Linear and Left Linear grammars, Conversion of FA into CFG and Regular grammar into FA, Simplification of CFG, Normal Forms- Chomsky Normal Form(CNF), Greibach Normal Form (GNF), Chomsky Hierarchy, Programming problems based on the properties of CFGs. Pumping Lemma for Context Free languages, Closure properties of CFL (proof required). |
Unit 3 |
Nondeterministic Pushdown Automata (NPDA)- Definition, Moves, A Language Accepted by NPDA, DPDA and DCFL, PDA for Context Free Languages, Context Free grammars for PDA, Two stack Pushdown Automata, Decision Problems of CFL, Programming problems based on the properties of CFLs. Equivalence of PDA and CFG, Overview of LEX and YACC. |
Unit 4 |
Basic Turing Machine Model, Representation, Language Acceptability, Techniques & Modifications, TM as Computer of Integer Functions, UTM, Linear Bounded Automata, Turing Church‘s Thesis, Recursive and recursively enumerable languages, Halting problem, Undecidability, Examples of Undecidable problem. |
Unit 5 |
Introduction to Complexity classes, Computability and Intractability, time complexity, P, NP, Co-NP, Proof of Cook‘s Theorem, Space Complexity, SPACE, PSPACE, Proof of Savitch‘s Theorem, L ,NL ,Co-NL complexity classes. |