10CS56 Formal Languages and Automata theory syllabus for IS


Part A
Unit-1 Introduction to Finite Automata 7 hours

Introduction to Finite Automata; The central concepts of Automata theory; Deterministic finite automata; Nondeterministic finite automata

Unit-2 Finite Automata, Regular Expressions 7 hours

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 6 hours

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 Context-Free Grammars And Languages 6 hours

Context –free grammars; Parse trees; Applications; Ambiguity in grammars and Languages

Part B
Unit-5 Pushdown Automata 7 hours

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 6 hours

Normal forms for CFGs; The pumping lemma for CFGs; Closure properties of CFLs

Unit-7 Introduction To Turing Machine 7 hours

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 6 hours

A Language that is not recursively enumerable; An Undecidable problem that is RE; Post’s Correspondence problem; Other undecidable problems.

Last Updated: Tuesday, January 24, 2023