Uploaded February 2018 | Updated November 2026, 5 days ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS6160 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs6160/ and other related videos at http://www.cs.virginia.edu/robins/videos.html
Specific topics covered in this lecture: review of pushdown automata / non-determinism / closure properties of CFLs / decidable properties of CFLs & CFGs / PDA enhancements. pumping revisited, cube-free and square-free strings, complementation revisited, "the truth - the whole truth - and nothing but the truth", Library of Babel
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS6160 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs6160/ and other related videos at http://www.cs.virginia.edu/robins/videos.html
Specific topics covered in this lecture: review of pushdown automata / non-determinism / closure properties of CFLs / decidable properties of CFLs & CFGs / PDA enhancements. pumping revisited, cube-free and square-free strings, complementation revisited, "the truth - the whole truth - and nothing but the truth", Library of Babel










