Theorem 5.2.1: If L is a context-free language, then there is a PDA M with L = Null(M). Furthermore, M can be chosen to have a single state.
Theorem 5.2.2: if L = Null(M) for PDA M, then L is context-free.
Corollary 5.2.3: every PDA is equivalent to a 1-state PDA using empty stack acceptance, or a 2-state PDA using final state acceptance.
Previous slide | Next slide | Back to first slide | View graphic version |