Recent questions tagged pushdown-automata

Which one of the following statements concerning pushdown automata is false?Here, "accept" means acceptance by empty stack.Every context-free language is accepted by some...

A PDA accepts exactly the strings over $\{a,b\}$ whose middle symbol is $a$. Which strings are accepted?$aba$ $aa$ $abb$ $baa$ $bab$ $baaaa$

A PDA accepts $L=\{0^{2n}1^n\mid n>0\}$. Which strings are accepted?$001$ $000011$ $0001$ $000000111$ $\epsilon$

Let $M$ be a PDA that accepts by empty stack. Every transition reads exactly one input symbol, and every transition either pushes one stack symbol or pops one stack symbo...

A PDA accepts the language $L=\{a^n b^m \mid m>n\ge 0\}$. Which of the following strings are accepted?$aabbb$ $bbbb$ $aaab$ $abb$ $\epsilon$

Let $M$ be a PDA that accepts by empty stack. Suppose every transition of $M$ reads exactly one input symbol, and every transition either pushes one stack symbol or pops ...

A PDA $P$ accepts a language by final state. We want to construct another PDA $P_1$ such that $N(P_1)=L(P)$, meaning $P_1$ accepts by empty stack exactly the language acc...

States $q_1$ and $q_4$ are final states. The PDA pushes one $a$ for every input $a$, pops one $a$ for every input $b$, and then reads any number of $c$'s. Which strings a...

The PDA first pushes either two or three $\#$ symbols for every input $0$, then pops one $\#$ for every input $1$. Which language is accepted? $\{0^n1^m \mid 2n\le m\le 3...

A PDA accepts properly nested strings over $\{(,),[,]\}$ by pushing every opening symbol and popping only when the closing symbol matches the top of stack. Which strings ...

Let $L=\{a^m b^n \mid m\le n\le 2m,\ m,n\ge 0\}$. Which strings belong to $L$?$\epsilon$ $ab$ $abb$ $aabbb$ $aabbbbb$ $aaabb$

For $L=\{w\in{a,b}^* \mid n_a(w)=2n_b(w)\}$, which invariant should a PDA maintain using stack symbols $A$ and $B$ for surplus?$n_a(\text{read})-2n_b(\text{read})=\#A-\#B...

Let $L=\{x?y \mid x,y\in{0,1}^*$ and $y=x^R\}$. Which of the following strings belong to $L$?$01?10$ $01?01$ $10?01$ $110?110$ $?$

For the language $L=\{w\in{a,b}^* \mid n_a(w)=n_b(w)\}$, which statements describe a correct PDA design idea?Use the stack to store the currently unmatched majority symbo...

Let $L=\{w\in{a,b}^*\mid w$ has even length and $w$ is not a palindrome$\}$. Which PDA idea correctly recognizes $L$?Push the first half of the input, nondeterministicall...

Which PDA strategy correctly accepts $L=\{a^i b^j c^k\mid i=j \text{ or } j=k\}$?Nondeterministically choose one of two branches.In branch $1$, compare $a$'s with $b$'s a...

For the language $L=\{a^n b^m\mid n\ge m\ge 0\}$, a PDA pushes one $A$ for every $a$ and pops one $A$ for every $b$. Which acceptance condition is correct?Accept when inp...

A PDA is designed for $L=\{a^n b^{n+1}\mid n\ge 0\}$. It pushes one $A$ for every $a$, pops one $A$ for every matching $b$, and consumes one extra $b$ when the stack top ...

Consider a PDA with transitions $:$$\delta(q_0,a,Z)=\{(q_0,AZ)\}$ $\delta(q_0,a,A)=\{(q_0,AA)\}$ $\delta(q_0,b,A)=\{(q_1,\epsilon)\}$  $\delta(q_1,b,A)=\{(q_1,\epsilon)\}...

Consider the PDA $P=(\{q,p\},\{0,1\},\{Z_0,X\},\delta,q,Z_0,\{p\})$ with transition rules:$\delta(q,0,Z_0)=\{(q,XZ_0)\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,...

Suppose $D$ is a DPDA that accepts $L(D)$ by final state. Let $D'$ be the same DPDA, but with final states changed from $F$ to $Q-F$. Is it always true that $L(D')=\overl...

Suppose a PDA has the transition rules $\delta(q_1,a,c)=\{(q_3,c)\}$ and $\delta(q_1,\epsilon,c)=\{(q_1,c)\}$. From the current configuration $(q_1,acbc,c\#Z)$, where the...

Consider an NPDA $(Q,\Sigma,\Gamma,\delta,q_0,z,F)$ where$Q=\{q_0,q_1,q_2,q_3\}$$\Sigma=\{a,b\}$$\Gamma=\{0,1\}$$z=0$$F=\{q_3\}$Suppose the transition rules include $\del...

Suppose an NPDA has the transition rule $\delta(q_1,a,b)=\{(q_2,cd),(q_3,\epsilon)\}$. If the current configuration is $(q_1,abb,bZ)$, where the stack is written top to b...

Which of the following languages cannot be accepted by push down automata?$\mathrm{L}=\left\{\mathrm{a}^\mathrm{n} \mathrm{b}^{n} c^\mathrm{n}: \mathrm{n} \geq 0\right\}$...

Question:LetL = { a^i b^j / i != 2j+1 } where i,j >=1  (a) Is LLL a deterministic context-free language (DCFL)?(b) Justify your answer with reasoning.

Consider the following languages:$L_{1}$ is the set of languages recognised by a deterministic pushdown automaton.$L_{2}$ is the set of languages recognised by a nondeter...