06CS56 - Formal Languages And Automata Theory |
PART – A |
UNIT 1 |
INTRODUCTION TO FINITE AUTOMATA: Introduction to Finite
Automata; The central concepts of Automata theory; Deterministic finite
automata; Nondeterministic finite automata. |
UNIT 2 |
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 |
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 |
TRANSMISSION MEDIA, ERROR DETECTION AND
CORRECTION: Twisted pair cable, Coaxial cable, Fiber-Optic cable,
Radio waves, Microwaves, Infrared. Introduction to error detection /
correction; Block coding; linear block codes; Cyclic codes, Checksum. |
PART – B |
UNIT 5 |
PUSHDOWN AUTOMATA: Definition of the Pushdown automata; The
languages of a PDA; Equivalence of PDA’s and CFG’s; Deterministic
Pushdown Automata. |
UNIT 6 |
PROPERTIES OF CONTEXT-FREE LANGUAGES: Normal forms for
CFGs; The pumping lemma for CFGs; Closure properties of CFL |
UNIT 7 |
INTRODUCTION TO TURING MACHINE: Problems that Computers
cannot solve; The turning machine; Programming techniques for Turning Machines; Extensions to the basic Turning Machines; Turing Machine and
Computers. |
UNIT 8 |
UNDECIDABILITY: A Language that is not recursively enumerable; An
Undecidable problem that is RE; Post’s Correspondence problem; Other
undecidable problems. |
REFERENCE |
TEXT BOOKS: |
1. Introduction to Automata Theory, Languages and Computation
– John E.. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman:, 3rd
Edition, Pearson education, 2007.
|
Reference Books |
1. Fundamentals of the Theory of Computation: Principles and
Practice – Raymond Greenlaw, H.James Hoove, Morgan
Kaufmann, 1998.
2. Introduction to Languages and Automata Theory – John C
Martin, 3rd Edition, Tata McGraw-Hill, 2007.
3. Introduction to Computer Theory – Daniel I.A. Cohen, 2nd
Edition, John Wiley & Sons, 2004.
4. An Introduction to the Theory of Computer Science, Languages
and Machines – Thomas A. Sudkamp, 3rd Edition, Pearson
Education, 2006. |