## Formal Languages and Automata Theory Syllabus for ¾ I.T(1st Sem)

### 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,
Normal Forms for DDDA’s, Closure Properties of DCFL’S, LR(k) Grammars, Properties of LR(k) Grammars.
5. Universal Turing Machines and Undecidability:
Design and Techniques for Construction of Turing Machines, Rice’s Theorem and Some Undecidable problems.
Greibaach Theorem, Undecidability of PCP. Chomsky Hierarchy, Regular Grammars, Unrestricted Grammars,
Context Sensitive Languages, Relationship between classes of Languages.
#### Prescribed Text book :

Introduction to Automata Theory, Languages & Computation By J.E.Hopcraft & Jeffery D.Ulman – Narosa Publishing Company.
#### Reference Books:

1)Theory of Computer Science By Mishra & Chandra Sekharan, PHI.
2)Mathematical Foundations of Computer Science By Beckman.
3)Mathematical Theory of Computation By Manna Z.
Go Back to Home page