Lemma 5.3.2: For each DPDA A, there is a DPDA B so that
(i) L(A) = L(B),
(ii) B scans each input sequence in its entirety.
Theorem 5.3.3: The complement of each deterministic context-free language L is a deterministic context- free language.
| Previous slide | Next slide | Back to first slide | View graphic version |