Uploaded February 2018 | Updated September 2026, 9 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: closure properties of context-free languages (CFLs): union / Kleene star / intersection with regular sets, non-closure under intersection and complementation, non-closure under infinite number of operator applications, decidable and undecidable properties of CFLs / PDAs / CFGs, PDA enhancements: 2-way / 2-stacks / queue automata / 2-heads / non-determinism, non-regularity, pumping theorem, misnomers about pumping, "prime" strings, pumping for CFLs
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: closure properties of context-free languages (CFLs): union / Kleene star / intersection with regular sets, non-closure under intersection and complementation, non-closure under infinite number of operator applications, decidable and undecidable properties of CFLs / PDAs / CFGs, PDA enhancements: 2-way / 2-stacks / queue automata / 2-heads / non-determinism, non-regularity, pumping theorem, misnomers about pumping, "prime" strings, pumping for CFLs
