The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged dpda
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 4 Question 32 (Page No. 213)
The proof of Lemma $2.41$ says that $(q, x)$ is a looping situation for a $DPDA \:P$ if when $P$ is started in state $q$ with $x \in \Gamma$ on the top of the stack, it never pops anything below $x$ and it never reads an input ... decidable, where $F = \{ \langle P, q, x \rangle \mid (q, x)\: \text{is a looping situation for P}\}$.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.6k
points)

7
views
michaelsipser
theoryofcomputation
dpda
decidability
proof
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 8.5 Question 2 (Page No. 362)
The purpose of this exercise is to show that a onestack machine with an endmarker on the input has no more power than a deterministic $PDA$. $L\$ is the concatenation of language $L$ with the language containing only the one string $\$ ... $q$ such that $P$,started in $ID\ (q,a,X_{i}X_{i+1}\cdot \cdot X_{n})$ will accept.
asked
Jul 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.6k
points)

4
views
ullman
theoryofcomputation
turingmachine
dpda
descriptive
0
votes
0
answers
3
Draw PDA for this
L = { a^m b^n c^k=m+n } Please draw PDA for this Language!
asked
Dec 12, 2018
in
Theory of Computation
by
Guilherme Zanini Mor
(
5
points)

63
views
theoryofcomputation
pushdownautomata
dpda
0
votes
1
answer
4
Introduction to computer theory
What should be the approach to draw the DFA  "All strings that have exactly one double letter in them" on symbols {a,b}.
asked
Nov 12, 2018
in
Theory of Computation
by
Jeevesh
(
323
points)

92
views
theoryofcomputation
finiteautomata
dpda
0
votes
1
answer
5
Push Down Automata
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack Then A)Ldf proper subset of Lef. B)Ldf = Lef. C)Lef proper subset of Ldf. D)None .
asked
Nov 6, 2018
in
Theory of Computation
by
Abhisek Tiwari 4
Loyal
(
5.2k
points)

110
views
theoryofcomputation
pushdownautomata
dpda
contextfreegrammars
0
votes
2
answers
6
Pushdown Automata
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
asked
Oct 25, 2018
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.5k
points)

135
views
theoryofcomputation
pushdownautomata
dpda
0
votes
0
answers
7
Pushdown Automata
asked
Oct 19, 2018
in
Theory of Computation
by
Sambhrant Maurya
Active
(
3.9k
points)

98
views
pushdownautomata
theoryofcomputation
dpda
0
votes
0
answers
8
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
asked
Jul 28, 2018
in
Theory of Computation
by
Matrix
(
159
points)

388
views
theoryofcomputation
pushdownautomata
contextfreelanguages
dpda
+1
vote
1
answer
9
ISRO CS 17
Consider the following statements about the context free grammar G = {S>SS , S>ab , S>ba , S>^} I. G is ambiguous II. G produces all strings with equal number of a's and b's III. G can be accepted by a deterministic PDA. Which combination below expresses all ... ? A) I only B) I and III C) II and II D) All I,II,III In a answer key shown answer D but II is not right.
asked
Jun 13, 2018
in
Theory of Computation
by
Nikhil Patil
Junior
(
505
points)

172
views
userisro2017
usermod
theoryofcomputation
dcfl
dpda
0
votes
1
answer
10
pushdownautomata
asked
Apr 23, 2018
in
Theory of Computation
by
sumitr
(
235
points)

84
views
theoryofcomputation
pushdownautomata
dpda
selfdoubt
0
votes
1
answer
11
Introduction to Computer Theory
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?
asked
Apr 13, 2018
in
Theory of Computation
by
The Capricorn
(
89
points)

86
views
theoryofcomputation
dpda
npda
+4
votes
0
answers
12
Introduction to Computer Theory
Construct a PDA for the language of all those strings in which the number of $b 's$ is double the number of $a 's$. $a$ and $b$ can occur in any order. For example: $L=\{\text{^}, abb, bab, bba, aabbbb, ababbb, abbbabb, abbbab, abbba, ...... \}$
asked
Mar 28, 2018
in
Theory of Computation
by
The Capricorn
(
89
points)

180
views
theoryofcomputation
npda
dpda
+2
votes
1
answer
13
Power of Pushdown Machines
Which is more powerful : 2way NonDeterministic Pushdown Machine(NDPDM) or 2way Deterministic Pushdown Machine(DPDM) ? (or) Do both machine models have the same power ?
asked
Mar 4, 2018
in
Theory of Computation
by
ankitgupta.1729
Boss
(
17k
points)

110
views
theoryofcomputation
pushdownautomata
dpda
npda
0
votes
1
answer
14
#peterlinz
How can we show that { anbm, m>= n+2} is deterministic ? for eg for a4b6 or in general ?
asked
Dec 11, 2017
in
Theory of Computation
by
Pawan Kumar 2
Active
(
4.2k
points)

50
views
dpda
+1
vote
2
answers
15
Arrange in the increasing order of power of following automata
Realtime DPDA with Null Store,Real time DPDA with final state, DPDA with NULL store,DPDA with final state, NPDA
asked
Dec 11, 2017
in
Theory of Computation
by
Durgesh Singh
Junior
(
755
points)

367
views
theoryofcomputation
pushdownautomata
dpda
npda
0
votes
0
answers
16
Push Down Automata
Consider the following statement: S: Set of languages accepted by DPDA by empty stack contain only those DCFL’s with prefix property. Please explain as why this sentence is wrong....
asked
Dec 1, 2017
in
Theory of Computation
by
shivangi5
Active
(
1.1k
points)

79
views
theoryofcomputation
pushdownautomata
dpda
+7
votes
1
answer
17
deterministic pushdown automataprefix property
How to find DPDA’s that accept by null stack? Someone explain the prefix property for DPDA,How can we use this property?
asked
Nov 2, 2017
in
Theory of Computation
by
set2018
Loyal
(
7.8k
points)

946
views
theoryofcomputation
selfdoubt
dpda
+2
votes
0
answers
18
DPDA: One Liners
1) Can a Deterministic PDA has two epsilon transition each reading different Stack symbol to perform a transition? 2) Can a transition be performed without reading Stack symbol at all. Like $ a, λ/ λ$?
asked
Oct 22, 2017
in
Theory of Computation
by
AskHerOut
Junior
(
941
points)

94
views
theoryofcomputation
pushdownautomata
dpda
0
votes
0
answers
19
Question Regarding DPDA acceptance inspired from GATE 2005 Question
The following question is a modified version of this question https://gateoverflow.in/3785/gate2005it38, in this GATE question they have NPDA, but I'm asking about DPDA Let D be a deterministic pushdown automaton (DPDA) with exactly one state ... . Both L(P) and N(P) are necessarily Σ*. Neither L(P) nor N(P) are necessarily Σ*.
asked
Sep 17, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.4k
points)

182
views
pushdownautomata
theoryofcomputation
finiteautomata
contextfreelanguages
dpda
0
votes
0
answers
20
Push Down Automata
draw a deterministic PDA for ambn where, m = 2n+1
asked
Sep 16, 2017
in
Theory of Computation
by
NIKU
(
163
points)

135
views
theoryofcomputation
pushdownautomata
dpda
+7
votes
2
answers
21
True or False Question regarding DPDA and prefix property
a) A DPDA which accepts by empty stack cannot accept all Regular Languages? b) All Regular Languages doesn't satisfy prefix property?
asked
Sep 16, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.4k
points)

906
views
theoryofcomputation
regularlanguages
pushdownautomata
dpda
contextfreelanguages
finiteautomata
+1
vote
1
answer
22
Deterministic Push Down Automata
What is main difference between Deterministic Push down automata and simple Push down automata ?
asked
Aug 15, 2017
in
Theory of Computation
by
ashutoshaay26
(
163
points)

476
views
theoryofcomputation
dpda
pushdownautomata
To see more, click for the
full list of questions
or
popular tags
.
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 CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged dpda
Recent Blog Comments
On an all, IT branch is not eligible then,or is...
What was the answer for checksum field in tcp...
@CSHuB You need to choose "systems" as post...
@cshub.....if you are branch computer engineering...
Hey all! I can't see the CS branch here? How...
50,741
questions
57,251
answers
198,058
comments
104,686
users