||Unit 1: (D. Goswami)
Introduction to the course. Texts and References are given.
Unit 2: (D. Goswami)
Alphabet, Strings, Languages, Finite Representation of languages, Regular Expressions.
Unit 3: (K. V. Krishna)
Context'free Grammars (CFGs) 'Formal definition, sentential forms, leftmost and rightmost derivations,, the language of a CFG. Derivation tree or Parse tree 'Definition, Relationship between parse trees and derivations. Parsing and ambiguity, Ambiguity in grammars and Languages. Regular grammars.
Unit 4: (D. Goswami)
Finite automata (FA) 'its behavior; DFA 'Formal definition, simplified notations (state transition diagram, transition table), Language of a DFA. NFA 'Formal definition, Language of an NFA, Removing, epsilon'transitions. Equivalence of DFAs and NFAs.
Unit 5: (K. V. Krishna)
Myhill'Nerode Theorem and minimization of finite automata
Unit 6: (D. Goswami)
Establishing the equivalence between regular languages, regular grammars and finite automata.
Unit 7: (K. V. Krishna)
2DFA, Moore and Mealy automata.
Unit 8: (K. V. Krishna)
Some closure properties of Regular languages 'Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc. Pumping lemma, proving languages to be non regular.
Unit 9: (D. Goswami)
Simplification of CFGs 'Removing useless symbols, epsilon' Productions, and unit productions, Normal forms 'CNF and GNF
Unit 10: (K. V. Krishna)
Some closure properties of CFLs 'Closure under union, concatenation, Kleene closure, substitution, homomorphism, reversal, intersection with regular set, etc. Pumping lemma.
Unit 11: (K. V. Krishna)
Pushdown automata and showing the equivalence between PDA and CFG.
Unit 12: (K. V. Krishna)
Turing Machines TM 'Formal definition and behavior, Transition diagrams, Language of a TM, TM as accepters and deciders. TM as a computer of integer functions. Variants of Turing machines.
Unit 13: (K. V. Krishna)
Grammars and grammatically computable functions.
Unit 14: (D. Goswami)
Recursive languages, Some properties of recursive and recursively enumerable languages, Codes for TMs. A language that is not recursively enumerable (the diagonalization language). The universal language, Undecidability of the universal language, The Halting problem, Undecidable problems about TMs.
Unit 15: (K. V. Krishna)
Time bounded TMs, The classes P, NP and NP'complete, Cook s Theorem, Some NP'complete problems.
Unit 16: (D. Goswami)
Context'sensitive languages, linear bounded automata and Chomsky Hierarchy.