 |
| Automata theory Formal Language Syllabus | IndianTechnoEra |
(Common for CSE, CSE with Specialization in Data Science)
(CSE with specialization in Cloud Technology & Information Security)
BCSE-515 (Formal Language & Automata Theory)
Course Objectives:
To provide fundamental understanding of the core concepts in automata theory and formal languages
To provide knowledge about how to design automata, regular expressions and context-free grammars accepting or generating a certain language
To learn the ability to describe the language accepted by automata or generated by a regular expression or a context-free grammar
To appreciate the power of the Turing Machine, as an abstract automaton, that describes computation, effectively and efficiently. v) To develop a view on the importance of computational theory.
Unit: 1
Introduction: Alphabet, languages and grammars, productions and derivation, Chomsky hierarchy of languages.
Regular languages and finite automata: Finite State System, 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, Closure properties of regular languages, pumping lemma for regular languages, minimization of finite automata.
Unit: 2
Context-free languages and pushdown automata: Context-free grammars (CFG) and languages (CFL), parse trees, ambiguity in CFG, removal of null & unit production, Chomsky and Greibach normal forms, pumping lemma for context-free languages, closure properties of CFLs, deterministic pushdown automata, nondeterministic pushdown automata (PDA) and equivalence with CFG.
Unit: 3
Introduction to Machines and Context-sensitive languages: Concept of basic machines, Properties and limitations of FSM, Moore and Mealy Machines, Equivalence of Moore and Mealy Machines, Context-sensitive grammars (CSG) and languages, Linear Bound Automata.
Unit: 4
Recursive enumerable languages and 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, Halting Problem of TM, PCP problem, universal Turing machine.
Course Outcome:
After completion of this course, students will be able to:
1. Acquire a fundamental understanding of the core concepts in automata theory and formal languages.
2. Design automata, regular expressions and context-free grammars accepting or generating a certain language.
3. Describe the language accepted by automata or generated by a regular expression or a context-free grammar.
4. Appreciate the power of the Turing Machine, as an abstract automaton, that describes computation, effectively and efficiently. v) Develop a view on the importance of computational theory.
Text Books:
1. John Martin, Introduction to Languages and The Theory of Computation, Tata McGraw Hill.
2. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia.
Reference Books:
1. Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia.
2. Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.
3. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.