Lecture and Seminary on Thursday, May 3, 2018
Section outline
-
Topics: - Emptiness and finiteness problems for context-free grammars
- Cocke, Kasami, Younger algorithm
- undecidable problems for context-free grammars (preview)
- deterministic pushdown automata (DPDA)
- deterministic context-free languages (DCFL)
- DCFL is closed under complementation
- Ogden's Lemma for DCFL and applications
-
-
The solutions to these problems are to be presented and discussed at the Seminary on May 10, 2018.
-
-