Three Types of
Acceptance: Equivalence
Theorem:
•L = L(Mf)f for
a PDA Mf Û L = L(Mfe)fe for a PDA Mfe
•L = L(Me)e for a PDA Me Û L = L(Mfe)fe for
a PDA Mfe
•L = L(Mf)f for
a PDA Mf Û L = L(Me)e for
a PDA Me
Note: There
exist these conversions:
PDA Mfe that accept L by final state and empty
pushdown
PDA Mf that accept L by final state
PDA Me that accept L by empty pushdown
31/50