|
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. |
| |