B.E (Engineering) Computer Science (CSE) free download

File name FAFL Notes [2010] (SJBIT).pdf

FORMAL LANGUAGES AND AUTOMATA THEORY 10CS56 FORMAL LANGUAGES AND AUTOMATA THEORY Subject Code: 10CS56 Hours/Week : 04 Total Hours : 52 I.A. Marks : 25 Exam Hours: 03 Exam Marks: 100 P ART - 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 . P ART ­ 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; Extensions to the basic Turning Machines; Turing Machine and Computers. UNIT ­ 8 6 Hours Undecidability: A that is not recursively enumerable; An Undecidable problem that is RE; Post's Correspondence problem; Other undecidable problems. Dept of ISE,SJBIT 1 FORMAL LANGUAGES AND AUTOMATA THEORY 10CS56 Text Books: 1. John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman: Introduction to Automata Theory, Languages and Computation, 3rd Edition, Pearson Education, 2007. (Chapters: 1.1, 1.5, 2.2 to 2.5, 3.1 to 3.3, 4, 5, 6, 7, 8.1 to 8.4, 8.6, 9.1, 9.2, 9.4.1, 9.5) Reference Books: 1. K.L.P. Mishra: Theory of Computer Science, Automata, Languages, and Computation, 3rd Edition, PHI, 2007. 2. Raymond Greenlaw, H.James Hoover: Fundamentals of the Theory of Computation, Principles and Practice, Morgan Kaufmann, 1998. Dept of ISE,SJBIT 2 FORMAL LANGUAGES AND AUTOMATA THEORY FLAT 10CS56 Table Of Contents UNIT-1:INTRODUCTION TO FINITE AUTOMATA: 1.1: Introduction to finite Automata 1.2 : Central concepts of automata theory 1.3: Deterministic finite automata 1.4:Non deterministic finite auto mata UNIT-2:FINITE AUTOMATA, REGULAR EXPRESSIONS 2.1 An application of finite auto mata 2.2 Finite automata with Epsilon transitions 2.3 Regular expressions 2.4 Finite automata and regular expressions 2.5Applications of Regular expressions UNIT- 3: PROPERTIES OF REGULAR LANGUAGES 3.1 Regular languages 3.2 proving languages not to be regular languages 3.3 closure properties of regular languages 3.4 decision properties of regu