Question Discussion & Solution

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?\a. {wcw^R ? w? {a,b}* } b. {ww^R ? w? {a,b,c}* }c. {aⁿbⁿcⁿ ? n ? 0 } d. {w ? w is a palindrome over {a,b,c} } Note: w^R  is the string obtained by reversing 'w'

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

If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations

|-* is the __________ closure of |-

PDA is more powerful than