Question Discussion & Solution

A push down automata is different than finite automata by

Which of the following statements is true?

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z₀, X} where Z₀ is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) ? (t, XZ₀) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z₀ and X (in that order) on the stack.
(s, a, Z₀) ? (s, XXZ₀)
(s, ?, Z₀) ? (f, ?)
(s, a, X) ? (s, XXX)
(s, b, X) ? (t, ?)
(t, b, X) ? (t,.?)
(t, c, X) ? (u, ?)
(u, c, X) ? (u, ?)
(u, ?, Z₀) ? (f, ?)
The language accepted by the PDA is

Let L_D  be the set of all languages accepted by a PDA by final state and L_F  the set of all languages accepted by empty stack. Which of the following is true?

PDA is more powerful than