TAF1901 | Welcome to Automata Theory | Why Study Automata? | Download | |
TAF1902 | Finite Automata | What are They? Who Needs ‘em? | Download | |
TAF1903 | Deterministic Finite Automata | Alphabets, Strings and Languages, Transition Graphs and Tables | Download | |
TAF1904 | Nondeterministic Finite Automata | Nondeterminism, Subset Construction, ε-Transitions | Download | |
TAF1905 | Regular Expressions | Definitions, Equivalence to Finite Automata | Download | |
TAF1906 | Applications of Regular Expressions | Unix RE’s, Text Processing, Lexical Analysis | Download | |
TAF1907 | Decision Properties of Regular Languages | General Discussion of “Properties”, The Pumping Lemma Membership, Emptiness, Etc. | Download | |
TAF1908 | Closure Properties of Regular Languages | Union, Intersection, Difference, Concatenation, Kleene Closure, Reversal, Homomorphism, Inverse Homomorphism | Download | |
TAF1909 | Context Free Grammars | Formalism, Derivations, Backus Naur Form Left and Rightmost Derivations | Download | |
TAF1910 | Parse Trees | Definitions, Relationship to Left and Rightmost Derivations Ambiguity in Grammars | Download | |
TAF1911 | Normal Forms for CFG’s | Eliminating Useless Variables, Removing Epsilon, Removing Unit Productions, Chomsky Normal Form | Download |
Automata Theory, Languages, and Computation 3rd Edition
By: Hopcroft, Motwani, Ullman
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