Automata Theory

Below is the syllabus for Automata Theory:-

Unit-I

Introduction to Automata: Study and Central Concepts of Automata Theory, Applications of Finite Automata, An Introduction of Deterministic Finite Automata(DFA) and Non-Deterministic Finite Automata(NFA), Finite Automata with Epsilon (€) Transitions.

Regular Expression and Languages:-Regular Expressions (RE), Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws of Regular Expressions. Closure Properties of Regular Languages, RE to NFA, DFA Conversion and DFA to RE, Equivalence, and Minimization of NFA and DFA automata.

Unit-2

Context-free Grammars and Languages: Parse Trees, Context-Sensitive Grammar, Applications of Context-Free Grammars, Regular Grammar, Ambiguity in Grammars and Languages. Normal forms of context-free grammars, Subfamilies of Context-Free Languages (CFL), Closure Properties of CFL, Chomsky Theorem, Chomsky Hierarchy, Chomsky Normal Form, Greibach Normal Form.

Pumping Lemma:-Introduction to Pumping Lemma, pumping lemma for context-free languages, Applications of Pumping Lemma, Minimization of Finite Automata, and Recursive Language.

Unit-3

Mealy and Moore Machines:- Definitions, Representation, Equivalence of Moore and Mealey Machines and it’s Designing.

Push Down Automata: Introduction of Push Down Automata (PDA), Language of PDA, Equivalence of PDA’s and CFG’s, Deterministic Push-Down Automata, Designing of PDA, Applications of PDA. Parikh Theorem and Parikh Mapping, Kleene’s Theorem.

Unit-4

Introduction to Turing Machine: The Turing Machine, Programming Techniques for Turing Machine, Extensions of Turing Machine, Restricted Turing Machines, Universal Turing Machines and Designing of Turing Machines, Time and Tape Complexity Measures of Turing machines           

Decidability:  Post’s Correspondence Problem (PCP), Rice’s Theorem, Decidability of Membership, Emptiness and Equivalence Problems of Languages.

Textbooks

1. J.E.Hopcroft, R.Motwani, and J.D.Ullman, “Introduction to Automata Theory Languages and computation”, Pearson Education Asia, 2001.
2. K.Krithivasan and R.Rama; Introduction to Formal Languages, Automata Theory, and Computation; Pearson Education, 2009.

References

1. Peter Linz, “An Introduction to Formal Language and Automata”, 4th Edition, Narosa Publishing house, 2006.
2. M.Sipser; Introduction to the Theory of Computation; Singapore: Brooks/Cole, Thomson Learning, 1997.
3. John.C.martin, “Introduction to the Languages and the Theory of Computation”, Third Edition, Tata McGraw-Hill, 2003.

Below is the link to download Automata Theory notes.