Uploaded February 2018 | Updated November 2026, 2 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: decidable properties of context-free langauges and grammars, CFL emptiness / finiteness, parsing, compilers, undecidable properties of context-free langauges and grammars, PDA minimality / equivalence, CFG minimality / ambiguity / equivalence, emptiness of intersection, inherent ambiguity, PDA enhancements, 2-way PDAs, 2-stack PDAs, queue automata, 2-head PDAs, non-deterministic PDAs, non-regular languages, pumping theorem, 0^n1^n, type errors revisited, the set of English words is regular
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: decidable properties of context-free langauges and grammars, CFL emptiness / finiteness, parsing, compilers, undecidable properties of context-free langauges and grammars, PDA minimality / equivalence, CFG minimality / ambiguity / equivalence, emptiness of intersection, inherent ambiguity, PDA enhancements, 2-way PDAs, 2-stack PDAs, queue automata, 2-head PDAs, non-deterministic PDAs, non-regular languages, pumping theorem, 0^n1^n, type errors revisited, the set of English words is regular










