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 |