 Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |
Course Co-ordinated by IIT Guwahati
 Coordinators IIT Guwahati IIT Guwahati

Untitled Document

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.
 Module No. & Module Name Topic No. of Hours 0. Introduction Lecture 1: Introduction 01 1. Languages and finite representation Lecture 1: Alphabet, Strings, Languages Lecture 2: Finite Representation 02 2. Grammars Lecture 1: Grammars (CFG) Lecture 2: Derivation Trees Lecture 3: Regular Grammars 03 3. Finite automata Lecture 1: Finite Automata Lecture 2: Nondeterministic Finite Automata Lecture 3: NFA <=> DFA 03 4. Minimization of finite automata Lecture 1: Myhill-Nerode Theorem Lecture 2: Minimization 02 5. RL ↔ RG ↔ FA Lecture 1: RE => FA Lecture 2: FA => RE Lecture 3: FA <=> RG 03 6. Variants of finite automata Lecture 1: Variants of FA 01 7. Properties of regular languages Lecture 1: Closure Properties of RL Lecture 2: Homomorphism Lecture 3: Pumping Lemma 03 8. Simplification of CFGs Lecture 1: Simplification of CFG Lecture 2: Normal Forms of CFG 02 9. Properties of CFLs Lecture 1: Properties of CFLs 01 10. Pushdown automata Lecture 1: Pushdown Automata Lecture 2: PDA <=> CFG 02 11. Turing machines Lecture 1: Turing Machines Lecture 2: Turing Computable Functions Lecture 3: Combining Turing Machines Lecture 4: Multi Input Lecture 5: Turing Decidable Languages Lecture 6: Variants of Turing Machines 06 12. Structured grammars Lecture 1: Structured Grammars 01 13. Decidability and undecidability Lecture 1: Decidability Lecture 2: Undecidability Lecture 3: Undecidability Lecture 4: Undecidability 04 14. Introduction to complexity theory Lecture 1: Time Bounded Turing Machines Lecture 2: P and NP Lecture 3: NP-Completeness Lecture 4: NP-Complete Problems Lecture 5: NP-Complete Problems Lecture 6: NP-Complete Problems 06 15. Chomsky Hierarchy Lecture 1: Chomsky Hierarchy 01 Total 41
1. J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson, 2001.

2. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1997/Pearson 1998.

3. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.

4. M. Sipser, Introduction to the Theory of Computation, Thomson Asia, 1997.

5. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.

 Important: Please enable javascript in your browser and download Adobe Flash player to view this site Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in