Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged npda
0
votes
0
answers
1
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.
anupamsworld
asked
in
Theory of Computation
Sep 2
by
anupamsworld
124
views
regular-grammar
context-free-grammar
npda
dpda
theory-of-computation
0
votes
0
answers
2
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
anupamsworld
asked
in
Theory of Computation
Sep 1
by
anupamsworld
69
views
npda
dpda
theory-of-computation
1
vote
1
answer
3
Applied Test Series
The language accepted by the given PDA is
LRU
asked
in
Theory of Computation
Oct 3, 2021
by
LRU
184
views
theory-of-computation
context-free-language
npda
test-series
0
votes
2
answers
4
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.
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 31, 2020
by
Lakshman Patel RJIT
717
views
nielit2017dec-assistanta
theory-of-computation
dpda
npda
0
votes
6
answers
5
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.
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
4.8k
views
nielit2017dec-scientistb
theory-of-computation
finite-automata
npda
dpda
0
votes
0
answers
6
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).
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
200
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
7
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
199
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
8
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,λ)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
220
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
205
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
10
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)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
238
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
1
answer
11
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
293
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
2
answers
12
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
917
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
13
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
164
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
14
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.$
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
167
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
1
answer
15
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$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
215
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
16
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$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
141
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
17
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
533
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
18
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^*)$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
190
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
19
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$}?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
121
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
20
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
157
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
npda
0
votes
0
answers
21
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
151
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
1
answer
22
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
338
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
23
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
261
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
24
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.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
164
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
25
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
211
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
26
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
144
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
27
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 =$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
233
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
0
answers
28
Peter Linz Edition 4 Exercise 7.1 Question 3 (Page No. 183)
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
372
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 7.1 Question 2 (Page No. 183)
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
117
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
1
answer
30
TESTBOOK TEST SERIES
WHAT WILL BE THE ANS?
Avik Chowdhury
asked
in
Theory of Computation
Oct 3, 2018
by
Avik Chowdhury
151
views
npda
Page:
1
2
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
RECRUITMENT IN OIL AND GAS CORPORATION LIMITED
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(647)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged npda
Recent Blog Comments
@abir_banerjee Thanks Abir. I'm third year...
@nolan_keats Currently I am in third year...
@abir_banerjee thank you Abir.Supposing you...
@nolan_keats just a suggestion as I also...
@abir_banerjee Hope I can do this in span of one...