Keyword Search
Advanced Search
Computer Science and Engineering  Theory of Automata, Formal Languages and Computation
Title: Theory of Automata, Formal Languages and Computation
Department: Computer Science and Engineering
Author: Prof. Kamala Krithivasan
University: IIT Madras
Type: WebLink
Abstract: 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.
Bodhbridge, Copyright © 2009 All rights reserved., is a portal by BodhBridge ESPL.