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 CFLs
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.