Study guide for Formal Languages and Automata Theory Comprehensive Examination

Coordinator: Phil Bernhard, .

Suggested Texts for Review:

• Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.
• Languages and Machines by Thomas Sudkamp

Concepts for Review:

• Mathematical Induction
• Countable and Uncountable Sets
• Diagonalization
• Recursive Definitions
• Deterministic Finite State Machines
• Non-Deterministic Finite State Machines
• Mealy Machines
• Push-down Automata
• Linear-Bounded Automata
• Turing Machines (Single and Multi-Tape, Multi-Track, etc.)
• Universal Turning Machines
• Regular Grammars
• Context-Free Grammars
• Context-Sensitive Grammars
• Unrestricted Grammars
• Greibach and Chomsky Normal Forms
• Pumping Lemma for Regular Languages
• Pumping Lemma for Context-Free Languages
• Regular Expressions
• Chomsky Hierarchy
• Closure Properties
• Decidable and Undecidable Problems
• The Halting Problem