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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged pushdownautomata
0
votes
1
answer
1
testbook test
Doubt 1: according to me L1 should be subset of L2. But answer is d) L1,L2,L3 are incomparable. Please explain this question to me Doubt 2: which type of language is L4?
asked
6 days
ago
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
1.9k
points)

29
views
testbooktestseries
theoryofcomputation
pushdownautomata
0
votes
0
answers
2
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
in
Theory of Computation
by
Matrix
(
59
points)

25
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dpda
0
votes
1
answer
3
UGC NET JULY 2018 Q34
asked
Jul 11
in
Theory of Computation
by
Sanjay Sharma
Boss
(
48.8k
points)

91
views
push
down
pushdownautomata
0
votes
0
answers
4
PDA Doubt
Please can anyone explain the PDA for reverse of a string via a transition graph
asked
Jun 29
in
Theory of Computation
by
Devshree Dubey
Boss
(
13.2k
points)

41
views
pushdownautomata
theoryofcomputation
+3
votes
1
answer
5
DCFL or Not
$\left \{ a^{m+n}b^{m+n}c^{n}m,n\geq 1 \right \}$ $\left \{ a^{m+n}b^{m+n}c^{k} m,n,k\geq 1\right \}$ $\left \{ a^{m+n}b^{m+k}c^{n+k} m,n,k\geq 1\right \}$ Which one DCFL, CFL or CSL?
asked
Jun 22
in
Theory of Computation
by
srestha
Veteran
(
91.9k
points)

186
views
theoryofcomputation
dcfl
contextfreelanguages
pushdownautomata
+1
vote
0
answers
6
Pda Automata
Why only stack data structure is used for implementing pushdown automata(pda) why not others ???
asked
Jun 3
in
Theory of Computation
by
vijju532
(
369
points)

30
views
theoryofcomputation
pushdownautomata
0
votes
1
answer
7
PDA for a language
$a^i b^j / i$ should not be equal to $2j+1$ give PDA for this language
asked
May 17
in
Theory of Computation
by
sanju77767
(
153
points)

70
views
theoryofcomputation
pushdownautomata
0
votes
1
answer
8
pushdownautomata
asked
Apr 23
in
Theory of Computation
by
sumitr
(
141
points)

35
views
theoryofcomputation
pushdownautomata
dpda
selfdoubt
0
votes
0
answers
9
Construct a NPDA (peter linz) Exercise 7.2.6
asked
Mar 25
in
Theory of Computation
by
Mk Utkarsh
Boss
(
14k
points)

126
views
theoryofcomputation
peterlinz
pushdownautomata
npda
0
votes
1
answer
10
Context free grammar and push down automata.
asked
Mar 21
in
Theory of Computation
by
hrcule
(
251
points)

91
views
theoryofcomputation
contextfreegrammars
pushdownautomata
+2
votes
1
answer
11
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
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
6.6k
points)

46
views
theoryofcomputation
pushdownautomata
dpda
npda
+4
votes
0
answers
12
Self doubt
Which of the following statement TRUE & also EXPLAIN WHY... (1) "Power of Turing Machine is Equal to Power of DFA with 2 Stack" (2) "Power of Turing Machine is Equal to Power of DFA with 2 Counter" (3) "Power of Push Down Automata is Equal ... DFA with 1 stack <= DFA with 2 counter <= DFA with 2 stack } (6) Power of Stack is More than power of Counter
asked
Jan 22
in
Theory of Computation
by
Harsh Mehta
Active
(
1.3k
points)

41
views
theoryofcomputation
turingmachine
pushdownautomata
finiteautomata
0
votes
0
answers
13
NonDeterministic PDA
I'm getting its equaltion {anbn  n > 0} U {a} U {b} But given is {anbn  n >= 0} U {a} U {b} Whether epsilon is accepted or not??
asked
Dec 24, 2017
in
Theory of Computation
by
Ashwin Kulkarni
Boss
(
17.8k
points)

116
views
pushdownautomata
npda
theoryofcomputation
+1
vote
3
answers
14
Is the following language CFL?
Not able to understand whether it is CFL or not due to the condition 'm>=481'.
asked
Dec 22, 2017
in
Theory of Computation
by
Ashish Sharma 3
(
353
points)

101
views
theoryofcomputation
contextfreelanguage
pushdownautomata
dcfl
contextfreelanguages
+1
vote
2
answers
15
DCFL or not??
$L1 = \bigl\{a^mb^nc^pd^q \mid m+q = n+p \bigr\}$ $L2 = \bigl\{a^mb^nc^pd^q \mid m+p = n+q \bigr\}$ 1. L1 is DCFL, L2 is not 2. L2 is DCFL, L1 is not 3. Both are not DCFL 4. Both are DCFL
asked
Dec 21, 2017
in
Theory of Computation
by
atul_21
Active
(
3.6k
points)

97
views
dcfl
pushdownautomata
contextfreelanguages
0
votes
1
answer
16
TOC PDA
Is my PDA right ?
asked
Dec 19, 2017
in
Theory of Computation
by
Pawan Kumar 2
Active
(
4.5k
points)

41
views
pushdownautomata
+1
vote
2
answers
17
Arrange in the increasing order of power of following automata
asked
Dec 11, 2017
in
Theory of Computation
by
Durgesh Singh
Junior
(
877
points)

126
views
theoryofcomputation
pushdownautomata
dpda
npda
0
votes
0
answers
18
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.4k
points)

56
views
theoryofcomputation
pushdownautomata
dpda
+2
votes
2
answers
19
[TOC] Basic doubt in DPDA
Following is the PDA that accept equal number of a and b. How can this be converted to DPDA? When stack top is Z,that it can read epsillon or a or b,which can create choice.So how can i remove choice in this and make it deterministic?
asked
Nov 21, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.5k
points)

137
views
theoryofcomputation
pushdownautomata
contextfreelanguage
deterministiccontextfreegrammars
0
votes
1
answer
20
Gate Sample 2018
Consider PDA = M = ({q0, q1}, {a, b}, {a, z0}, δ, q0, z0, φ) which accepts by empty stack δ: (q0, a, z0) = (q0, az0) (q0, a, a) = (q0, aa) (q0, b, a) = (q1, a) (q1, b, a) = (q1, a) (q1, a, a) = (q1, ε) (q1, ... given corresponds to the language ={/ >0,>0} how ? in transition 4th line (q1, b, a) = (q1, a) we dont perform pop operation for a then how is explanation correcT?
asked
Nov 19, 2017
in
Theory of Computation
by
Pranav Madhani
Junior
(
905
points)

117
views
gate2018
theoryofcomputation
practice
pushdownautomata
+1
vote
1
answer
21
a^n b^n c^m d^n e^n Is it CFG?
asked
Nov 11, 2017
in
Theory of Computation
by
Avdhesh Singh Rana
Active
(
3.2k
points)

261
views
theoryofcomputation
contextfreelanguage
pushdownautomata
+1
vote
1
answer
22
TOC: PDA as transudcer
Can PDA be used as transducer?
asked
Nov 9, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.5k
points)

56
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
23
ace test series
unable to understand 2nd point:
asked
Nov 4, 2017
in
Theory of Computation
by
raviyogi
Active
(
2.6k
points)

92
views
pushdownautomata
acetestseries
theoryofcomputation
+1
vote
1
answer
24
Pushdown Automata Question
i) I, II, III ii) I, II only iii) I only iv) none of the above
asked
Oct 29, 2017
in
Theory of Computation
by
kash0611
(
255
points)

158
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
25
PDA Construction
1)What is the main difference while drawing the PDA of {an bn  n>=0 } and {an bn  n>=1} ? 2)How does PDA changes when we have 0 in it as a constraint . 3)For all other cases how does the PDA changes on inclusion of 0.
asked
Oct 29, 2017
in
Theory of Computation
by
ashwina
Active
(
2k
points)

57
views
pushdownautomata
+1
vote
1
answer
26
PDA Doubt
In the below diagram which solution is correct and why ?
asked
Oct 29, 2017
in
Theory of Computation
by
ashwina
Active
(
2k
points)

53
views
theoryofcomputation
pushdownautomata
0
votes
0
answers
27
Problem while making a PDA
I feel it difficult to know when to change the state while making a PDA. Could anyone tell me in detailed manner when to cahnge the state . Below is the solution to a problem , could anyone tell me which one is more appropriate with justification.
asked
Oct 29, 2017
in
Theory of Computation
by
ashwina
Active
(
2k
points)

18
views
theoryofcomputation
pushdownautomata
+2
votes
0
answers
28
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
(
907
points)

41
views
theoryofcomputation
pushdownautomata
dpda
+1
vote
1
answer
29
Pushdown Automata: acceptance of a string
asked
Oct 2, 2017
in
Theory of Computation
by
AskHerOut
Junior
(
907
points)

136
views
theoryofcomputation
pushdownautomata
+1
vote
2
answers
30
Draw PDA for this
L = {cambndn} Please draw PDA for this Language!
asked
Sep 19, 2017
in
Theory of Computation
by
iarnav
Loyal
(
7.9k
points)

130
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dcfl
Page:
1
2
3
4
next »
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
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged pushdownautomata
Recent Blog Comments
gate overflow books are awesome; every one should ...
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
Yes, their tracking system is incomplete. ...
38,102
questions
45,600
answers
132,203
comments
49,188
users