Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged npda
0
votes
0
answers
1
Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
raj_uddeshya157
67
views
raj_uddeshya157
asked
Dec 27, 2023
Theory of Computation
theory-of-computation
gate-preparation
dcfl
dpda
npda
context-free-language
+
–
1
votes
1
answer
2
PDA,DCFL and CFL
Sourin Kundu
228
views
Sourin Kundu
asked
Jul 4, 2023
Theory of Computation
theory-of-computation
npda
dpda
context-free-language
+
–
0
votes
0
answers
3
PDA
i need to construct PDA for L = {a^m b^n: m>= n-5} L = {w belongs to {a,b}*: w has twice as many a’s as b’s}
i need to construct PDA for L = {a^m b^n: m>= n-5}L = {w belongs to {a,b}*: w has twice as many a’s as b’s}
moe12leb
241
views
moe12leb
asked
Jan 21, 2023
Theory of Computation
theory-of-computation
npda
+
–
0
votes
0
answers
4
PDA | TOC | Practice Question
Identify the type of the given language and draw the corresponding automata for the language. $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$ A] Regular B] DCFL C] CFL but not DCFL D] Non-CFL Please describe your selection.
Identify the type of the given language and draw the corresponding automata for the language.$L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$A] RegularB...
anupamsworld
511
views
anupamsworld
asked
Sep 2, 2022
Theory of Computation
regular-grammar
context-free-grammar
npda
dpda
theory-of-computation
+
–
0
votes
0
answers
5
PDA | TOC | Practice Question | Unacademy Class
Construct PDA using empty stack method for the given language. $L=\left \{ x \space\ | \space\ x\in \left \{ a,b \right \}^{*} ; n_{a}(x) >= n_{b}(x) \right \}$ //number of a’s is greater than or equal to number of b’s
Construct PDA using empty stack method for the given language.$L=\left \{ x \space\ | \space\ x\in \left \{ a,b \right \}^{*} ; n_{a}(x) >= n_{b}(x) \right \}$//number of...
anupamsworld
262
views
anupamsworld
asked
Sep 1, 2022
Theory of Computation
npda
dpda
theory-of-computation
+
–
1
votes
1
answer
6
Applied Test Series
The language accepted by the given PDA is
The language accepted by the given PDA is
LRU
280
views
LRU
asked
Oct 3, 2021
Theory of Computation
theory-of-computation
context-free-language
npda
test-series
+
–
0
votes
2
answers
7
NIELIT 2017 DEC Scientific Assistant A - Section B: 6
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
Which of the following statements is true ?Melay and Moore machines are language acceptors.Finite State automata is language translator.NPDA is more powerful than DPDA.Me...
admin
1.1k
views
admin
asked
Mar 31, 2020
Theory of Computation
nielit2017dec-assistanta
theory-of-computation
dpda
npda
+
–
0
votes
6
answers
8
NIELIT 2017 DEC Scientist B - Section B: 39
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
Which of the following is true?Mealy and Moore machine are language acceptors.Finite State automata is language translator.NPDA is more powerful than DPDA.Melay machine i...
admin
5.9k
views
admin
asked
Mar 30, 2020
Theory of Computation
nielit2017dec-scientistb
theory-of-computation
finite-automata
npda
dpda
+
–
0
votes
0
answers
9
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
379
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
10
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
291
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
11
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
307
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
12
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
282
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
13
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
393
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
14
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
475
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
15
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
16
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
209
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
17
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
257
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
18
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
295
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
19
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
195
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
20
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
708
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
21
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
248
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
22
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
191
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
23
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
230
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
24
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
211
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
25
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
509
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
26
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
337
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
27
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
355
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
28
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
402
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
29
Peter Linz Edition 4 Exercise 7.1 Question 5 (Page No. 183)
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.
Naveen Kumar 3
218
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
30
Peter Linz Edition 4 Exercise 7.1 Question 4 (Page No. 183)
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} : n ≥ 0, m ≥ 0$}. (d) $L =$ ... . (h) here (i) $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.
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^...
Naveen Kumar 3
338
views
Naveen Kumar 3
asked
Apr 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register