**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. |