Definition: Let M = (Q, S, G, R,
s, S,
F) be a PDA.
1) The language
that M accepts by final state,
denoted
by L(M)f , is defined as
L(M)f = {w: w Î S*, Ssw |–* zf, z Î G*, f Î F}
2) The language
that M accepts by empty pushdown, denoted by L(M)e, is defined
as
L(M)e = {w: w Î S*, Ssw |–* zf, z = e, f Î Q}
3) The language
that M accepts by final state and empty
pushdown, denoted by L(M)fe, is defined as L(M)fe = {w: w Î S*, Ssw |–* zf, z = e, f Î F}