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

 
Dr. K.V. Krishna
IIT Guwahati

 

Download Syllabus in PDF format



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