CS500 | Advanced Theory of Automata
  • Rating: 4.85
  • (439)
Course overview

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

What you will learn
Finite Automata
Deterministic and Nondeterministic Finite Automata, Finite Automata with Epsilon Transitions
Regular Expressions & Languages
Finite Automata and Regular Expressions, Applications and Algebraic Laws for Regular Expressions
Properties of Regular Expressions
Closure Properties, Decision Properties, Equivalence and Minimization of Automata
Context-Free Grammar & Languages
Context-Free Grammar, Parse Trees, Applications of CFGs, Ambiguity in Grammar and Languages
Pushdown Automata
Language of a PDA, Equivalence of PDA and CFG, Deterministic Pushdown Automata
Properties of Context-Free Languages
Normal Forms of CFGs, Pumping Lemma for CFG, Closure Properties, Decision Properties
Turing Machines
Programming Techniques of Turing Machines, Extensions and Restrictions, Computers
Undecidability
An Undecidable Problem That is RE, Undecidable Problems of Turing Machines, Post's Correspondence Problem
Course program
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
Lessons Name Description Duration Week Slides
1 Automata Theory Why Study Automata? 3 hours 1 TAF1901
2 Finite Automata What are They? Who Needs 'em? 3 hours 2 TAF1902
3 Deterministic Finite Automata Alphabets, Strings and Languages, Transition Graphs and Tables 3 hours 3 TAF1903
4 Nondeterministic Finite Automata Nondeterminism, Subset Construction, Epsilon-Transitions 3 hours 4 TAF1904
5 Regular Expressions Definitions, Equivalence to Finite Automata 3 hours 5 TAF1905
6 Applications of Regular Expressions Unix RE's, Text Processing, Lexical Analysis 3 hours 6 TAF1906
7 Decision Properties of Regular Languages General Discussion of "Properties", The Pumping Lemma Membership, Emptiness, Etc. 3 hours 7 TAF1907
8 Closure Properties of Regular Languages Union, Intersection, Difference, Concatenation, Kleene Closure, Reversal, Homomorphism, Inverse Homomorphism 3 hours 8 TAF1908
9 Context Free Grammars Formalism, Derivations, Backus Naur Form Left and Rightmost Derivations 6 hours 9,10 TAF1909
10 Parse Trees Definitions, Relationship to Left and Rightmost Derivations Ambiguity in Grammars 3 hours 11 TAF1910
11 Normal Forms for CFG's Eliminating Useless Variables, Removing Epsilon & Unit Productions, Chomsky Normal Form 3 hours 12 TAF1911
12 Pushdown Automata PDA, Language of PDA, Determinitic PDA 6 hours 13,14 TAF1912
13 Pumping Lemma for CFL's Statement and Applications 3 hours 15 TAF1913