Page 33 - M.Sc. Mathematics

SASTRA Deemed to be University M. Sc. Mathematics
_________________________________________________________________________

Course Code: MAT506 L T P C
Semester: IV 4 0 0 4

FINITE AUTOMATA & FORMAL LANGUAGES

Course Objective: Expose the students to understand the concepts such as finite state
machines, pushdown automata and Turing machines.

UNIT I: Finite Automata 12 periods
Deterministic finite automaton: Deterministic finite automaton and transition graphs –
languages and DFAs – Regular languages - Non deterministic finite automaton - Definition of
NFA - Equivalence of deterministic and non deterministic finite automata – reduction of the
number of states in finite automata.

UNIT II: Regular Languages and Regular Grammar 12 periods
Regular expressions: Formal definition of RE – languages associated with RE - Connection
between regular expressions and regular languages – closure properties of regular
languages - Identifying some non regular languages using pumping lemma
.
UNIT III: Context Free Languages, Simplifications and Normal Forms 12 periods
Context free grammars - Parsing and ambiguity - Simplifications - Two normal forms.

UNIT IV: Pushdown Automata and Properties of CFL 12 periods
Non deterministic pushdown automata - PA and CFL - Deterministic PA and deterministic
CFL - Properties of CFL - Decision algorithms - A pumping lemma for CFL - A pumping
lemma for linear languages.

UNIT V: Turing Machines 12 periods
The standard Turing machine - Minor variations on the Turing machine theme – Non
deterministic Turing machines - A universal Turing machine - linear bounded automata - A
Language that is not recursively enumerable – Undecidable problems about Turing
Machines – Other undecidable problems.- NP hard and NP complete problems with
examples.

Text Book:

John E. Hopcroft and Jeffery D. Ullman. Introduction to Automata Theory, Languages and
Computation, Narosa Publishing House, 2002.

Reference Books:

1. An introduction to formal languages and automata, Peter Linz, Fourth Edition, Narosa
Publishing House, New Delhi, 2006.
2. Introduction to languages and the Theory of Computation, J.C.Martin, Tata McGraw
Hill Publishing Co. Ltd.
3. Michael Sipser, Introduction to the Theory of Computation, Wadsworth Publishing Co
Inc; 3rd edition (29 June 2012)

- 33 -