Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged pushdown-automata
0
votes
0
answers
31
Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more powerful (recognize a larger class of languages) than ... $3-PDAs$ are not more powerful than $2-PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more power...
admin
278
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
pushdown-automata
finite-automata
descriptive
+
–
1
votes
0
answers
32
Michael Sipser Edition 3 Exercise 2 Question 47 (Page No. 159)
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v...
admin
780
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
descriptive
+
–
0
votes
0
answers
33
Peter Linz Edition 4 Exercise 7.2 Question 18 (Page No. 196)
Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1. Theorem 7.1: For any context-free language L, there exists an npda M such that L = L (M).
Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1.Theorem 7.1: For any context-free language L, there exists an npda ...
Naveen Kumar 3
399
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
34
Peter Linz Edition 4 Exercise 7.2 Question 17 (Page No. 196)
Give full details of the proof of Theorem 7.2 . Theorem 7.2 : If L = L (M) for some npda M, then L is a context-free language.
Give full details of the proof of Theorem 7.2 .Theorem 7.2 : If L = L (M) for some npda M, then L is a context-free language.
Naveen Kumar 3
300
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
35
Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
Find a context-free grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions $δ(q_0, a,z) =$ {$(q_0, Az)$}, $δ (q_0,b, A) =$ {$(q_0, AA)$}, $δ(q_0, a, A) =$ {$(q_1,λ)$}.
Find a context-free grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions ...
Naveen Kumar 3
316
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
36
Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
Naveen Kumar 3
289
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
37
Peter Linz Edition 4 Exercise 7.2 Question 11,12,13 (Page No. 195)
Show that the npda in Example 7.8 accepts L (aa*b). Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b). show that the variable ($q_0zq_1$) is useless. (see page no. 191-193) Example 7.8 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
Show that the npda in Example 7.8 accepts L (aa*b).Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b).show that the v...
Naveen Kumar 3
403
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
1
votes
1
answer
38
Peter Linz Edition 4 Exercise 7.2 Question 10 (Page No. 195)
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.
Naveen Kumar 3
493
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
1
votes
2
answers
39
Peter Linz Edition 4 Exercise 7.2 Question 9 (Page No. 195)
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.
Naveen Kumar 3
1.4k
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
40
Peter Linz Edition 4 Exercise 7.2 Question 7,8 (Page No. 195)
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$. Show how the number of states of $\widehat M $ in the above exercise can be reduced to two.
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$.Show how the number of states of $\wideh...
Naveen Kumar 3
214
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
41
Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$
Naveen Kumar 3
267
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
1
answer
42
Peter Linz Edition 4 Exercise 7.2 Question 4 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.
Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.
Naveen Kumar 3
307
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
43
Peter Linz Edition 4 Exercise 7.2 Question 3 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.
Naveen Kumar 3
201
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
44
Peter Linz Edition 4 Exercise 7.2 Question 2 (Page No. 195)
Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.
Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.
Naveen Kumar 3
190
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
+
–
0
votes
0
answers
45
Peter Linz Edition 4 Exercise 7.2 Question 1 (Page No. 195)
Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the language generated by the given grammar. Example 7.6: Construct a pda that accepts the language generated by a grammar with productions $S\rightarrow aSbb|a.$
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...
Naveen Kumar 3
196
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
+
–
0
votes
0
answers
46
Peter Linz Edition 4 Exercise 7.1 Question 16 (Page No. 184)
We can define a restricted npda as one that can increase the length of the stack by at most one symbol in each move, changing Definition 7.1 so that $\delta :$Q x $(\sum \cup$ {$\lambda$}$) $ ... the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.
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 $\...
Naveen Kumar 3
718
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
47
Peter Linz Edition 4 Exercise 7.1 Question 14 (Page No. 184)
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.
Naveen Kumar 3
251
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
48
Peter Linz Edition 4 Exercise 7.1 Question 13 (Page No. 184)
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 in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?
Naveen Kumar 3
202
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
49
Peter Linz Edition 4 Exercise 7.1 Question 11 (Page No. 184)
What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) with transitions $\delta(q_0,a,z)=${$(q_1,a),(q_2,\lambda)$}, $\delta(q_1,b,a)=${$(q_1,b)$}, $\delta(q_1,b,b)=${$(q_1,b)$}, $\delta(q_1,a,b)=${$(q_2,\lambda)$} ?
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_...
Naveen Kumar 3
246
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
npda
+
–
0
votes
0
answers
50
Peter Linz Edition 4 Exercise 7.1 Question 10 (Page No. 184)
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)=${$(q_1,1z)$}, $\delta(q_0,b,1)=${$(q_1,11)$}, $\delta(q_2,a,1)=${$(q_3,\lambda)$}, $\delta(q_3,a,1)=${$(q_4,\lambda)$} $\delta(q_4,a,z)=${$(q_4,z),(q_5,z)$} ?
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)=...
Naveen Kumar 3
218
views
Naveen Kumar 3
asked
Jun 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
1
votes
1
answer
51
pda self doubt
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack. DPDA with empty stack accepts LR(0) grammar. Can someone explain in depth/or give good reference links?
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack.DPDA with empty stack accepts LR(0) grammar.Can someone explain in depth/...
manisha11
627
views
manisha11
asked
May 13, 2019
Theory of Computation
pushdown-automata
pushdown-automata
+
–
0
votes
0
answers
52
Michael Sipser Edition 3 Exercise 2 Question 12 (Page No. 156)
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 equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
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...
admin
460
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
+
–
0
votes
0
answers
53
Michael Sipser Edition 3 Exercise 2 Question 11 (Page No. 155)
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,$ using the procedure given in $\text{Theorem 2.20.}$
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...
admin
305
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
+
–
0
votes
0
answers
54
Michael Sipser Edition 3 Exercise 2 Question 10 (Page No. 155)
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 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\}.$
admin
996
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
+
–
1
votes
0
answers
55
Michael Sipser Edition 3 Exercise 2 Question 7 (Page No. 155)
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 language $\{a^{n}b^{n}|n\geq 0\}$ $\{w\#x|w^{R}$ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
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...
admin
316
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
+
–
0
votes
0
answers
56
Michael Sipser Edition 3 Exercise 2 Question 5 (Page No. 155)
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| w contains at least three 1's}}$ ... $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
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| ...
admin
862
views
admin
asked
May 1, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
+
–
0
votes
1
answer
57
Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}),with ...
Naveen Kumar 3
539
views
Naveen Kumar 3
asked
Apr 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
58
Peter Linz Edition 4 Exercise 7.1 Question 8 (Page No. 183)
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.
Naveen Kumar 3
343
views
Naveen Kumar 3
asked
Apr 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
59
Peter Linz Edition 4 Exercise 7.1 Question 7 (Page No. 183)
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.
Naveen Kumar 3
379
views
Naveen Kumar 3
asked
Apr 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
0
votes
0
answers
60
Peter Linz Edition 4 Exercise 7.1 Question 6 (Page No. 183)
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$}.
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$}.
Naveen Kumar 3
413
views
Naveen Kumar 3
asked
Apr 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
Page:
« prev
1
2
3
4
5
6
7
8
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register