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.