Consider the pushdown automaton (PDA) below which runs over the input alphabet $(a, b, c)$. It has the stack alphabet $\{Z_0, X\}$ where $Z_0$ 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) \rightarrow (t, XZ_0)$ 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_0$ and $X$ (in that order) on the stack.
$(s, a, Z_0) \rightarrow (s, XXZ_0)$
$(s, \epsilon, Z_0) \rightarrow (f, \epsilon)$
$(s, a, X) \rightarrow (s, XXX)$
$(s, b, X) \rightarrow (t, \epsilon)$
$(t, b, X) \rightarrow (t,\epsilon)$
$(t, c, X) \rightarrow (u, \epsilon)$
$(u, c, X) \rightarrow (u, \epsilon)$
$(u, \epsilon, Z_0) \rightarrow (f, \epsilon)$
The language accepted by the PDA is
- $\{a^lb^mc^n \mid l = m = n\}$
- $\{a^l b^m c^n \mid l = m\}$
- $\{a^lb^mc^n \mid 2l = m + n\}$
- $\{a^lb^mc^n \mid m = n\}$