Introduction to Finite Automata, Structural Representations, Automata and Complexity. The Central Concepts of Automata Theory. Deterministic Finite Automata, Nondeterministic Finite Automata, An Application: Text Search, Finite Automata with Epsilon-Transitions.

Regular Expressions, Finite Automata and Regular Expressions, Proving Languages not to be Regular. Closure Properties of Regular Languages, Equivalence and Minimization of Automata, Applications of Regular Expressions.

Context-Free Grammars, Parse Trees, Ambiguity in Grammars and Languages, Ambiguity in Grammars and Languages, Definition of the Pushdown Automaton, The Languages of a PDA, Equivalence of PDA’s and CFG’s, Deterministic Pushdown Automata.

Normal Forms for Context-Free Grammars, The Pumping Lemma for Context-Free Languages, Closure Properties of Context-Free Languages.

Introduction to Turing Machines: Problems That Computers Cannot Solve, The Turing Machine, Programming Techniques for Turing Machines, Extensions to the Basic Turing Machine, Undecidability: A Language That Is Not Recursively Enumerable.