Subjects Taught

Back to Subjects

CS500 | Advanced Theory of Automata

Welcome to Automata Theory Why Study Automata? Download
Finite Automata What are They? Who Needs ‘em? Download
Deterministic Finite Automata Alphabets, Strings and Languages, Transition Graphs and Tables Download
Nondeterministic Finite Automata Nondeterminism, Subset Construction, ε-Transitions Download
Regular Expressions Definitions, Equivalence to Finite Automata Download
Applications of Regular Expressions Unix RE’s, Text Processing, Lexical Analysis Download
Decision Properties of Regular Languages General Discussion of “Properties”, The Pumping Lemma Membership, Emptiness, Etc. Download
Closure Properties of Regular Languages Union, Intersection, Difference, Concatenation, Kleene Closure, Reversal, Homomorphism, Inverse Homomorphism Download
Context Free Grammars Formalism, Derivations, Backus Naur Form Left and Rightmost Derivations Download
Parse Trees Definitions, Relationship to Left and Rightmost Derivations Ambiguity in Grammars Download
Normal Forms for CFG’s Eliminating Useless Variables, Removing Epsilon, Removing Unit Productions, Chomsky Normal Form Download
Advanced Theory of Automata

Automata Theory, Languages, and Computation 3rd Edition
By: Hopcroft, Motwani, Ullman

Course Info

The course introduces advance concepts in automata theory and formal languages including grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine.

Finite automata, including the deterministic and nondeterministic versions | Regular expressions, their equivalence to finite automata, properties of the languages defined by regular expressions and finite automata | Context-free grammars and languages | Pushdown automata, their equivalence to context-free grammars, properties of context-free languages, introduction to Turing machines | Turing machines, decidability, undecidable problems | The classes P and NP, NP-complete problems


Course Aim
  • Finite automata, including the deterministic and nondeterministic versions
  • Regular expressions, their equivalence to finite automata, properties of the languages defined by regular expressions and finite automata
  • Context-free grammars and languages
  • Pushdown automata, their equivalence to context-free grammars, properties of context-free languages, introduction to Turing machines
  • Turing machines, decidability, undecidable problems
  • The classes P and NP, NP-complete problems

Learning Outcomes
  • Learn how to deal formally with discrete systems
  • Improve skills at proving facts, especially inductive proofs
  • Understanding inductive proofs to formulate a reason why a method works
  • Gain experience with abstract models and constructions
  • Learn the process of simulation across models as the modern approach to programming in layered abstractions