Uploaded February 2018 | Updated September 2026, 7 hours ago

---

This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html

Specific topics covered in this lecture: equivalence of regular languages and regular expressions, regular expression identities, decidable properties of finite automata, language emptiness, language finiteness, finite automata equivalence, context-free grammars, context-free languages, palindromes, well-balanced parenthasis, ambiguity in English / languages / programming / art