FORMAL LANGUAGES AND AUTOMATA THEORY
Subject Code: 10CS56
I.A. Marks : 25
Hours/Week : 04
Exam Hours: 03
Total Hours : 52
Exam Marks: 100
PART - A
UNIT – 1 7 Hours
Introduction to Finite Automata: Introduction to Finite Automata; The
central concepts of Automata theory; Deterministic finite automata;
Nondeterministic finite automata
UNIT – 2 7 Hours
Finite Automata, Regular Expressions: An application of finite automata;
Finite automata with Epsilon-transitions; Regular expressions; Finite
Automata and Regular Expressions; Applications of Regular Expressions
UNIT – 3 6 Hours
Regular Languages, Properties of Regular Languages: Regular
languages; Proving languages not to be regular languages; Closure properties
of regular languages; Decision properties of regular languages; Equivalence
and minimization of automata
UNIT – 4 6 Hours
Context-Free Grammars And Languages : Context –free grammars; Parse
trees; Applications; Ambiguity in grammars and Languages .
PART – B
UNIT – 5 7 Hours
Pushdown Automata: Definition of the Pushdown automata; the languages
of a PDA; Equivalence of PDA’s and CFG’s; Deterministic Pushdown
Automata
UNIT – 6 6 Hours
Properties of Context-Free Languages: Normal forms for CFGs; The
pumping lemma for CFGs; Closure properties of CFLs
UNIT – 7 7 Hours
Introduction To Turing Machine: Problems that Computers cannot solve;
The turning machine; Programming techniques for Turning Machines;
42
Extensions to the basic Turning Machines; Turing Machine and Computers.
UNIT – 8 6 Hours
Undecidability: A Language that is not recursively enumerable; An
Undecidable problem that is RE; Post’s Correspondence problem; Other
undecidable problems.