Question Discussion & Solution

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

A regular Grammar is a _________

If the PDA does not stop on an accepting state and the stack is not empty, the string is:

A DPDA is a PDA in which: