Introduction to Finite Automata; The central concepts of Automata theory; Deterministic finite automata; Nondeterministic finite automata.
An application of finite automata; Finite automata with Epsilon-transitions; Regular expressions; Finite Automata and Regular Expressions;Applications of Regular Expressions.
Regular languages; Proving languages not to be regular languages; Closure properties of regular languages; Decision properties of regular languages; Equivalence and minimization of automata.
Context –free grammars; Parse trees; Applications; Ambiguity in grammars and Languages.
Definition of the Pushdown automata; The languages of a PDA; Equivalence of PDA’s and CFG’s; Deterministic Pushdown Automata.
Normal forms for CFGs; The pumping lemma for CFGs; Closure properties of CFL
Problems that Computers cannot solve; The turning machine; Programming techniques for Turning Machines; Extensions to the basic Turning Machines; Turing Machine and Computers.
A Language that is not recursively enumerable; An Undecidable problem that is RE; Post’s Correspondence problem; Other undecidable problems.