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.

TEXT BOOK: Sections 1.1, 1.5, 2.2,2.3,2.4,2.5

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

TEXT BOOK: Sections 3.1, 3.2 (Except 3.2.1), 3.3, 4.1, 4.2, 4.4

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.

TEXT BOOK: Sections 5.1, 5.2, 5.4, 6.1,6.2,6.3.1,6.4

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

TEXT BOOK: Sections 7.1, 7.2, 7.3

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.

TEXT BOOK: Sections 8.1,8.2, 8.3,8.4, 9.1, 9.2