Recent questions tagged pushdown-automata

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 mark...

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?$\{a^nb^nc^n \mid n ≥ 0\}$$\{a^lb^mc^n \mid l ...

Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the...

Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata?$\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$$\lef...

Let $M=(\{q_0, q_1\}, \{0, 1\}, \{z_0, X\}, \delta, q_0, z_0, \phi)$ be a Pushdown automation where $\delta$ is given by$\delta(q_0, 1, z_0) = \{(q_0, Xz_0)\}$$\delta(q_0...

Which one of the following is FALSE?There is a unique minimal DFA for every regular languageEvery NFA can be converted to an equivalent PDA.Complement of every context-fr...

Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.

Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?$L_1 = L...