CS21004: Formal Language And Automata Theory
| CS21004 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Formal Language And Automata Theory | ||||||||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
| Semester | Spring | ||||||||||||||||||||||||||||
Syllabus
Syllabus mentioned in ERP
Introduction: Alphabet, languages and grammars, productions and derivation, Chomsky hierarchy of languages. Regular languages and finite automata: Regular expressions and languages, deterministic finite automata (DFA) and equivalence with regular expressions, nondeterministic finite automata (NFA) and equivalence with DFA, regular grammars and equivalence with finite automata, properties of regular languages, pumping lemma for regular languages, minimization of finite automata. Context-free languages and pushdown automata: Context-free grammars (CFG) and languages (CFL), Chomsky and Greibach normal forms, nondeterministic pushdown automata (PDA) and equivalence with CFG, parse trees, ambiguity in CFG, pumping lemma for context-free languages, deterministic pushdown automata, closure properties of CFLs. Context-sensitive languages: Context-sensitive grammars (CSG) and languages, linear bounded automata and equivalence with CSG. Turing machines: The basic model for Turing machines (TM), Turing-recognizable (recursively enumerable) and Turing-decidable (recursive) languages and their closure properties, variants of Turing machines, nondeterministic TMs and equivalence with deterministic TMs, unrestricted grammars and equivalence with Turing machines, TMs as enumerators. Undecidability: Church-Turing thesis, universal Turing machine, the universal and diagonalization languages, reduction between languages and Rice s theorem, undecidable problems about languages. References 1.Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia. 2.John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia. 3.Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer. 4.Michael Sipser, Introduction to the Theory of Computation, PWS Publishing. 5.John Martin, Introduction to Languages and The Theory of Computation, Tata
�McGraw Hill.
Concepts taught in class
The course covers various important concepts like finite state machine (automata), Turing machine and regex. This also serves as the foundation course for the Theory of Computation course that CSE UG have in 7th semester.