Recent questions tagged pushdown-automata

Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.

Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.

Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the languagegenerated by the given grammar.Example 7.6: Construct a pda that accepts...

We can define a restricted npda as one that can increase the length of the stack by at most onesymbol in each move, changing Definition 7.1 so that $\...

Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.

What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?

What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) withtransitions $\delta(q_0,a,z)=${$(q_1...

What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}),with $\delta(q_0,b,z)=...

Convert the $CFG$ $G$$R\rightarrow XRX \mid S$$S\rightarrow aT b \mid bT a$$T\rightarrow XT X \mid X \mid\epsilon$$X\rightarrow a \mid b$ to an eq...

Convert the $CFG$ $G_{4}$ $E\rightarrow E+T\mid T$$T\rightarrow T\times F\mid F$$F\rightarrow (E)\mid a$ to an equivalent $PDA,$ usin...

Give an informal description of a pushdown automaton that recognizes the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$

Give informal English descriptions of PDAs for the following languages.The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$The complement of the lang...

Give informal descriptions and state diagrams of pushdown automata for the languages in the following languages In all parts, the alphabet $\sum$ is $\{0,1\}.$$\text{{w| ...

Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.

Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.

Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.

Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.

Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}.(a) $L =$ {$a^nb^{2n} : n ≥ 0$}.(b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}.(c) $L =$ {$a^nb^mc^{n+m}...

Construct npda's that accept the following regular languages.(a) $L_1 = L (aaa^*b)$.(b) $L_1 = L (aab^*aba^*)$.(c & d here)

Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.

Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

Show that the language $L=\{0^{n}1^{n}|n\geq 1\}\cup \{0^{n}1^{2n}|n\geq 1\}$is a context-free language that is not accepted by any $DPDA$ Hint$:$ Show that there must ...

We can prove Theorem $6.19$ in three parts$:$Show that if $L=N(P)$ for some $DPDA$ $P,$ then $L$ has the prefix property.Show that if $L=N(P)$ for some $DPDA$ $P,$ then...

Give deterministic pushdown automata to accept the following languages$:$$\{0^{n}1^{m}|n\leq m\}$$\{0^{n}1^{m}|n\geq m\}$$\text{\{$0^{n}1^{m}0^{n}$|n and m are arbitrary\...

For each of the following PDA's, tell whether or not it is deterministic. Either show that it meets the definition of a DPDA or find a rule or rules that violate it.$a)$ ...

Suppose we have a PDA with $s$ states $t$ stack symbols and no rule in which a replacement stack string has a length greater than $u.$ Give a tight upper bound on the num...

Show that if $P$ is a PDA, then there is a one-state PDA $,P_{1},$ such that $N(P_{1})=N(P).$

Below are some context-free languages.For each,devise a PDA that accepts the language by empty stack. You may ,if you wish, first construct a grammar for the language, an...