Syllabus of Andhra University BTech Information Technology - IT 3.1.4 - Formal Languages and Automata Theory

Third year - First Semester

Instruction: 3 Periods & 1 Tut /week
Univ. Exam : 3 Hours

Sessional Marks: 30
Univ-Exam-Marks:70

1. Finite Automata and Regular Expressions:

Basic Concepts of Finite State Systems, Deterministic and Non-Deterministic FiniteAutomata, Finite Automata with e-moves, Regular Expressions, Minimization of FiniteAutomata, 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 FiniteAutomata.

3. Context Free Grammars and Languages:

Context Free Grammars and Languages, Derivation Trees, Simplification of ContextFree 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 Sensitivelanguages,Relationship between classes of languages.

Text Books:

Introduction to Automata Theory,Languages & Computation By J.E.Hopcraft & JefferyD.Ulman – Narosa Publishing Company.

Reference Books:

Theory of Computer Science By Mishra & Chandra Sekharan, PHI.

An Introduction To Formal Languages and Automata,3e By Peter Linz – Narosa Publishing House.