frmCourseSyllabusIPDownload.pdf

CSE322:FORMAL LANGUAGES AND AUTOMATION THEORY L:3 T:0 P:0 Credits:3 Course Outcomes: Through this course students should be able to CO1 :: Understand Concepts and Abstractions...

CSE322:FORMAL LANGUAGES AND AUTOMATION THEORY L:3 T:0 P:0 Credits:3 Course Outcomes: Through this course students should be able to CO1 :: Understand Concepts and Abstractions for Automata as a Fundamental Computational Model CO2 :: Understand algebraic formalisms of languages such as regular expressions, context-free grammar. CO3 :: Compare different types of Grammars and design context free grammars for formal languages CO4 :: Analyze the properties and structure of context-free languages CO5 :: understand Understand the construction of Push Down Automata, including closure properties and their relationship with parsing techniques. CO6 :: Understand algorithms and computability through the lens of Turing machines and relationship between various computational models Unit I FINITE AUTOMATA : Definition and Description of a Finite Automaton, Deterministic and Non- deterministic Finite State Machines, Transition Systems and Properties of Transition Functions, Acceptability of a String by a Finite Automaton, The Equivalence of DFA and NDFA, Mealy and Moore Machines, Minimization of Finite Automata, Basics of Strings and Alphabets, Transition Graph and Properties of Transition Functions, Regular Languages, The Equivalence of Deterministic and Non- deterministic Finite Automata Unit II REGULAR EXPRESSIONS AND REGULAR SETS : Regular Expressions and Identities for Regular Expressions, Finite Automata and Regular Expressions: Transition System Containing null moves, NDFA with null moves and Regular Expressions, Conversion of Non-deterministic Systems to Deterministic Systems, Algebraic Methods using Arden's Theorem, Construction of Finite Automata Equivalent to a Regular Expression, Equivalence of Two Finite Automata and Two Regular Expressions, Closure Properties of Regular Sets, Pumping Lemma for Regular Sets and its Application, Equivalence between regular languages: Construction of Finite Automata Equivalent to a Regular Expression, Properties of Regular Languages, Non-deterministic Finite Automata with Null Moves and Regular Expressions, Myhill-Nerode Theorem Unit III FORMAL LANGUAGES : Derivations and the Language Generated by a Grammar, Definition of a Grammar, Chomsky Classification of Languages, Languages and their Relation, Recursive and Recursively Enumerable Sets, Languages and Automata, Chomsky hierarchy of Languages REGULAR GRAMMARS : Regular Sets and Regular Grammars, Converting Regular Expressions to Regular Grammars, Converting Regular Grammars to Regular Expressions, Left Linear and Right Linear Regular Grammars Unit IV CONTEXT- FREE LANGUAGES : Ambiguity in CFG, Leftmost and rightmost derivations, Language of a CFG, Sentential forms, Applications of CFG, Pumping Lemma for CFG, Derivations Generated by a Grammar, Construction of Reduced Grammars, Elimination of null and unit productions, Normal Forms for CFG: Chomsky Normal Form SIMPLIFICATION OF CONTEXT- FREE GRAMMARS : Construction of Reduced Grammars, Greibach Normal Form Unit V PUSHDOWN AUTOMATA AND PARSING : Description and Model of Pushdown Automata, Representation of PDA, Acceptance by PDA, Pushdown Automata: NDPDA and DPDA, Context free languages and PDA, Pushdown Automata and Context-Free Languages, Comparison of deterministic and non-deterministic versions, closure properties, LL (k) Grammars and its Properties, LR(k) Grammars and its Properties, PARSING: Top-Down and Bottom-Up Parsing Unit VI Session 2024-25 Page:1/2 Unit VI TURING MACHINES AND COMPLEXITY : Turing Machine Model, Representation of Turing Machines, Design of Turing Machines, The Model of Linear Bounded Automaton, Power of LBA, Variations of TM, Non-Deterministic Turing Machines, Halting Problem of Turing Machine, Post Correspondence Problem, Basic Concepts of Computability, Decidable and Undecidable languages, RECURSIVELY ENUMERABLE LANGUAGE, Computational Complexity: Measuring Time & Space Complexity, Power of Linear Bounded Automaton, Variations of Turing Machine, Cellular automaton Text Books: 1. THEORY OF COMPUTER SCIENCE: AUTOMATA, LANGUAGES & COMPUTATION by K.L.P. MISHRA & N. CHANDRASEKARAN, PRENTICE HALL References: 1. THEORY OF COMPUTATION: A PROBLEM SOLVING APPROACH by KAVI MAHESH, WILEY 2. THEORY OF COMPUTATION by RAJESH K. SHUKLA, CENGAGE LEARNING 3. AUTOMATA, COMPUTABILITY AND COMPLEXITY: THEORY AND APPLICATIONS by ELAINE RICH, PEARSON 4. AN INTRODUCTIONTO FORMAL LANGUAGES AND AUTOMATA by PETER LINZ, JONES & BARTLETT LEARNING 5. INTRODUCTION TO THEORY OF AUTOMATA, FORMAL LANGUAGES AND COMPUTATION by SATINDER SINGH CHAHAL, GULJEET KAUR CHAHAL, A.B.S.PUBLICATION, JALANDHAR 6. INTRODUCTION TO THE THEORY OF COMPUTATION by MICHAEL SIPSER, CENGAGE LEARNING 7. FORMAL LANGUAGES AND AUTOMATION THEORY by STEFAN HOLLOS, J. RICHARD HOLLOS, ABRAZOL PUBLISHING 8. INTRODUCTION TO FORMAL LANGUAGES, AUTOMATA THEORY AND COMPUTATION by KAMALA KRITHIVASAN, RAMA R., PEARSON 9. INTRODUCTION TO AUTOMATA THEORY, LANGUAGES, AND COMPUTATION by HOPCROFT, MOTWANI, ULLMAN, PEARSON 10. CELLULAR AUTOMATA MACHINES: A NEW ENVIRONMENT FOR MODELING by TOMMASO TOFFOLI, MIT Press 11. AN INTRODUCTION TO AUTOMATA THEORY AND FORMAL LANGUAGES. by ADESH K. PANDEY, S.K. KATARIA & SONS Session 2024-25 Page:2/2