Theory of Computation (CS3102), Lecture 11, Professor Gabriel Robins, Spring 2018

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