(L(Ax).
Now M accepts x if and only if L(M x) = Ø. Hence, the decidability
of the membership problem for pushdown automata follows from the
decidability of the emptiness problem for pushdown automata (Theorem
3.6.1).
3.6.2 Given an instance (M, x) of the membership problem a finite state
automaton Ax can be constructed to accept just x. By the proof of Theorem
3.5.1 a pushdown automaton M x can be constructed to accept L(M ) (L(Ax).
Now M accepts x if and only if L(M x) = Ø. Hence, the decidability
of the membership problem for pushdown automata follows from the
decidability of the emptiness problem for pushdown automata (Theorem
3.6.1).
3.6.3 From a given finite state transducer M a pushdown automaton A can be constructed such that A accepts an empty language if and only if M has at most one output on each input. The pushdown automaton A on a give input x nondeterministically simulates two computations of M as input x. The pushdown automaton A discards the outputs of M, but keeps track of the difference in their lengths. The pushdown automaton A accepts x if and only if it determines that the simulated computations produce outputs of either differnt lengths or of different character at a given location.
3.6.4 A pushdown automaton A can be constructed to accept an input of the form x#yrev if and only if the given finite state transducer M has output y or input x.