Grammars - Production systems - Chomskian Hierarchy - Right linear grammar and
Finite state automata - Context free grammars - Normal forms - uvwxy theorem – Parikh
mapping - Self embedding property - Subfamilies of CFL - Derivation trees and
ambiguity.

Finite state Automata - Non deterministic and deterministic FSA, NFSA with ε-
moves, Regular Expressions - Equivalence of regular expression and FSA .

Pumping
lemma , closure properties and decidability. Myhill - Nerode theorem and
minimization - Finite automata with output.

Pushdown automata - Acceptance by empty store and final state - Equivalence between
pushdown automata and context-free grammars - Closure properties of CFL -
Deterministic pushdown automata.

Turing Machines - Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Godel numbering - Universal Turing Machine - Recursively enumerable sets and recursive sets - Computable functions - time space complexity measures - context sensitive languages and linear bound automata.

Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages.

Time and tape complexity measures of Turing machines; Random access machines; the classes P and NP; NP-Completeness; satisfiability and Cook's theorem; Polynomial reduction and some NP-complete problems.

Advanced topics; Regulated rewriting L systems; Grammar systems.

New paradigms of computing; DNA computing; Membrane computing.

Module No.

Topics

No. of Hours

1

Grammars, Languages generated, Chomskian Hierarchy, CFG, Ambiguity, Reduced grammars, Normal forms

7

2

FSA,NFSA, NFSA with € moves, Regular expressions, Equivalence of regular expression and FSA, Equivalence of type 3 grammars and FSA, Pumping lemma , Closure and decidability results , Myhill- Nerode theorem, Minimization, FSA with output, Problems

11

3

Pushdown Automata, Acceptance by final state and empty store, Equivalence to CFG , Deterministic PDA

4

4

Problems and Solutions

3

5

Turing Machines - Construction, Techniques of TM construction , TM as acceptor and i/o device , Problems . Generalized and restricted versions.

Peter Linz, "An Introduction to Formal
Language and Automata", 4th Edition, Narosa
Publishing house , 2006.

M.Sipser; Introduction to the Theory of
Computation; Singapore: Brooks/Cole,
Thomson Learning, 1997.

John.C.martin, "Introduction to the Languages
and the Theory of Computation",Third edition,
Tata McGrawHill, 2003.

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