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