Uploaded February 2018 | Updated September 2026, 1 hour 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: Kleene, Chomsky, formal languages, definitions, alphabets, strings, languages, concatenation, exponentiation, union, intersection, Kleene closure, Sigma-star, complementation