Section: Lecture and Seminary on Thursday, May 3, 2018 | Automata and Grammars NTIN071 | DL 1

DL 1

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
- Select activity AuGLecture11
  
  AuGLecture11 File
  
  Slides for Lecture 11
  
  (Update: May 3, 2018)
- Select activity SS2018_A11
  
  SS2018_A11 File
  
  The solutions to these problems are to be presented and discussed at the Seminary on May 10, 2018.
- Select activity SS2018_A11_SOL
  
  SS2018_A11_SOL File
  
  This file contains solutions to selected problems from Assignment 11.