Alphabets, languages; Regular Languages: various types of finite automata and their equivalences thereof, minimization of finite automata, Myhill-Nerode theorem, regular expressions, regular grammars, closure properties of regular languages, pumping lemma, algorithmic properties of regular languages;

Context-free languages: context-free grammars, derivation trees, ambiguous grammars, Chomsky and Greibach normal form, nondeterministic and deterministic pushdown automata, pumping lemma and Ogden’s lemma, closure and algorithmic properties of context-free languages, Top-down and Bottom-up parsing;

Context sensitive languages: context sensitive grammars, linear bounded automata; Turing machines: recursively enumerable languages, unrestricted grammars, variants of Turing machines and equivalence thereof. Undecidability.

Module No.

Topic/s

Lectures

1

Introduction; alphabets, Strings and Languages; automata and Grammars

2

2

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

3

3

Regular expressions (RE) -Definition, FA and RE, RE to FA, FA to RE, algebraic laws for RE, applications of REs. Regular grammars and FA, FA for regular grammar, Regular grammar for FA

3

4

Proving languages to be non-regular -Pumping Lenma, applications. Some closure properties of Regular languages -Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc. Myhill-Nerode theorem

3

5

DFA Minimization. Some decision properties of Regular languages -emptiness, finiteness, membership, equivalence of two DF As or REs, etc. Two-way finite automata, Finite automata with output

3

6

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

3

7

Pushdown Automata (PDA) -Formal definition, behavior and graphical notation, Instantaneous descriptions (Ids), The language of PDA (acceptance by final state and empty stack). Equivalence of acceptance by final state and empty stack, Equivalence of PDAs and CFGs, CFG to PDA, PDA to CFG.

3

8

DPDAs -Definition, DPDAs and Regular Languages, DPDAs and CFLs. Languages of DPDAs, DPDAs, and ambiguous grammars. Top-down and Bottom-up parsing.

3

9

Simplification of CFGs -Removing useless symbols, epsilon- Productions, and unit productions, Normal forms -CNF and GNF

3

10

Proving that some languages are not context free -Pumping lemma for CFLs, applications. Some closure properties of CFLs -Closure under union, concatenation, Kleene closure, substitution, homomorphism, reversal, intersection with regular set, etc. Some more decision properties of CFLs, Review of some undecidable CFL problems.

4

11

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. Programming techniques for TMs -Storage in state, multiple tracks, subroutines, etc. Variants of TMs -Multitape TMs, Nondeterministic TMs. TMs with semi-infinite tapes, multistack machines. Equivalence of the various variants with the basic model

6

12

Recursive and recursively enumerable 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.

2

13

Post's Correspondence Problem (PCP) -Definition, Undecidability of PCP. Other undecidability problems e.g. some problems related to CFLs

2

14

Context sensitive language and linear bounded automata. Chomsky hierarchy

2

Introductory Level Discrete Mathematics

J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson, 2001.

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

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

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

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