Formal Languages And Automata Theory Syllabus
Periods/week : 3 Periods & 1 Tut /week. Ses. : 30 Exam : 70 Examination (Practical): 3hrs. Credits: 4
1. Finite Automata and Regular Expressions:
Basic Concepts of Finite State Systems, Deterministic and Non-Deterministic Finite Automata, Finite Automata with e-moves, Regular Expressions, Minimization of Finite Automata, Mealy and Moore Machines, Two-Way Finite Automate.
2. Regular sets & Regular Grammars:
Basic Definitions of Formal Languages and Grammars, Regular Sets and Regular Grammars, Closure Properties of Regular Sets, Pumping Lemma for Regular Sets, Decision Algorithm for Regular Sets, Myhill-Nerode Theorem, Minimization of Finite Automata.
3. Context Free Grammars and Languages:
Context Free Grammars and Languages, Derivation Trees, Simplification of Context Free Grammars, Normal Forms, Pumping Lemma for CFL, closure properlties of CFL’s, Decision Algorithm for CFL.
4. Push down Automata and Deterministic CFL:
Informal Description, Definitions, Push-Down Automata and Context free Languages, Parsing and Push-Down Automata.
5. Universal Turing Machines and Undecidability:
Design and Techniques for Construction of Turing Machines, Undecidability of PCP. Chomsky Hierarchy, Regular Grammars, Unrestricted Grammars, Context Sensitive languages,Relationship between classes of languages.
TEXT BOOKS: Introduction to Automata Theory, Languages & Computation By J.E.Hopcraft & Jeffery D.Ulman – Narosa Publishing Company.
Theory of Computer Science By Mishra & Chandra
An Introduction To Formal Languages and Automata,3e By Peter Linz – Narosa Publishing House.