###### Mathematics  Formal Languages and Automata Theory
 List Lectures   [ 1 ]  2  3  4  5
 # Lecture Name 1 Introduction 2 Alphabet, Strings, Languages 3 Finite Representation 4 Grammars (CFG) 5 Derivation Trees 6 Regular Grammars 7 Finite Automata 8 Nondeterministic Finite Automata 9 NFA <=> DFA 10 Myhill'Nerode Theorem

 Title: Formal Languages and Automata Theory Department: Mathematics Author: Dr. K.V. Krishna Dr. Diganta Goswami University: IIT Guwahati Type: WebLink Abstract: Unit 1: (D. Goswami) Introduction to the course. Texts and References are given. Unit 2: (D. Goswami) Alphabet, Strings, Languages, Finite Representation of languages, Regular Expressions. Unit 3: (K. V. Krishna) 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. Regular grammars. Unit 4: (D. Goswami) 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. Unit 5: (K. V. Krishna) Myhill'Nerode Theorem and minimization of finite automata Unit 6: (D. Goswami) Establishing the equivalence between regular languages, regular grammars and finite automata. Unit 7: (K. V. Krishna) 2DFA, Moore and Mealy automata. Unit 8: (K. V. Krishna) Some closure properties of Regular languages 'Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc. Pumping lemma, proving languages to be non regular. Unit 9: (D. Goswami) Simplification of CFGs 'Removing useless symbols, epsilon' Productions, and unit productions, Normal forms 'CNF and GNF Unit 10: (K. V. Krishna) Some closure properties of CFLs 'Closure under union, concatenation, Kleene closure, substitution, homomorphism, reversal, intersection with regular set, etc. Pumping lemma. Unit 11: (K. V. Krishna) Pushdown automata and showing the equivalence between PDA and CFG. Unit 12: (K. V. Krishna) 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. Variants of Turing machines. Unit 13: (K. V. Krishna) Grammars and grammatically computable functions. Unit 14: (D. Goswami) Recursive 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. Unit 15: (K. V. Krishna) Time bounded TMs, The classes P, NP and NP'complete, Cook s Theorem, Some NP'complete problems. Unit 16: (D. Goswami) Context'sensitive languages, linear bounded automata and Chomsky Hierarchy.