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
Lists
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
0
answers
1
Pushdown Automata
asked
1 day
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

38
views
pushdownautomata
theoryofcomputation
dpda
0
votes
0
answers
2
Context Free Grammar
Consider the following CFG 'G' S> aA/bSS/SS A> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked
2 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

17
views
theoryofcomputation
contextfreegrammars
contextfreelanguage
cfg
pushdownautomata
0
votes
0
answers
3
CFL with Empty Stack or Final State
$1)$"We can solve same PDA with empty stack and using final state" Can give an example of such language? Where is the difference between solving a pda with empty stak and by accepting final state? I got this link but without ... acceptancebyemptystackandfinalstate $2)$If language has prefix property, why it cannot be solved with empty stack?
asked
Oct 4
in
Theory of Computation
by
srestha
Veteran
(
98.5k
points)

45
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
4
Self doubt Pushdown Automata
Is it required to initialize stack symbol in PDA? If yes then does this PDA have valid transitions?
asked
Sep 20
in
Theory of Computation
by
Mk Utkarsh
Boss
(
20.2k
points)

11
views
pushdownautomata
theoryofcomputation
0
votes
1
answer
5
Pushdown automata
L={ai bj  i ≠ 2j+1} please give PDA for this language
asked
Sep 16
in
Theory of Computation
by
sanju77767
(
275
points)

25
views
pushdownautomata
+1
vote
0
answers
6
Michael sipser
I read this excerpt from sipser book We write a,b → c to signify that when the machine is reading an a from the input, it may replace the symbol b on the top of the stack with a c. Any of a, b, and c may be ε. If a is ε, the machine ... using any stack symbol as written here that top of stack might be epsilon if we don't want to consume it. If someone can clear my doubt. Thanks
asked
Sep 15
in
Theory of Computation
by
sushmita
Boss
(
14.7k
points)

10
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
7
Push down automata
Consider following PDA WHICH OF FOLLOWING IS TRUE ABOUT LANGUAGE ACCEPTED BY IT ? A. Regular but infinite B. Regular but finite C. DCFL but not regular D. CFL but not DCFL
asked
Sep 9
in
Theory of Computation
by
Na462
Loyal
(
6.5k
points)

51
views
theoryofcomputation
pushdownautomata
0
votes
0
answers
8
self doubt
Consider the Context free language which has equal no of as and bs. eg abab Since a proper prefix ab also belongs to this language, this language does not satisfy prefix property as far as i understand. But we can clearly draw a deterministic PDA ... with empty stack for CFL without prefix property. But above example forms a contradiction. Please resolve my doubt. I am getting confused.
asked
Sep 8
in
Theory of Computation
by
sushmita
Boss
(
14.7k
points)

53
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
9
Push Down Automata
Consider A given PDA as following Qo is the start state here. What is the language accepted by the given PDA ? 1. { ( bn a bn a )m  m,n ≥ 0 } 2. { ( bn a bn a )m  m,n ≥ 0 } U { bn  n ≥ 1} 3. { ( bn a bn )m . a  m,n ≥ 0 } 4. None
asked
Sep 5
in
Theory of Computation
by
Na462
Loyal
(
6.5k
points)

45
views
theoryofcomputation
pushdownautomata
0
votes
1
answer
10
PDADoubt
what is the DPDA for L=$a^{2n+1}b^n$  n>1
asked
Sep 3
in
Theory of Computation
by
aditi19
Junior
(
863
points)

113
views
pushdownautomata
0
votes
0
answers
11
PDADoubt
L=$a^mb^n$  m!=n is the following DPDA correct for the mentioned language?
asked
Sep 3
in
Theory of Computation
by
aditi19
Junior
(
863
points)

23
views
pushdownautomata
contextfreelanguage
0
votes
0
answers
12
DoubtPDA
what is the PDA for {L=$a^mb^n$ m>n}
asked
Sep 2
in
Theory of Computation
by
aditi19
Junior
(
863
points)

66
views
pushdownautomata
theoryofcomputation
contextfreelanguage
0
votes
0
answers
13
Parsing
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?
asked
Aug 31
in
Compiler Design
by
Mizuki
Junior
(
839
points)

29
views
compilerdesign
parsing
contextfreelanguage
pushdownautomata
theoryofcomputation
0
votes
1
answer
14
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
Aug 12
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
1.9k
points)

36
views
testbooktestseries
theoryofcomputation
pushdownautomata
0
votes
0
answers
15
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
(
63
points)

40
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dpda
0
votes
1
answer
16
UGCNETJuly2018II33
A pushdown automata behaves like a Turing machine when the number of auxiliary memory is 0 1 1 or more 2 or more
asked
Jul 13
in
Theory of Computation
by
Pooja Khatri
Active
(
4.3k
points)

32
views
ugcnetjuly2018ii
theoryofcomputation
pushdownautomata
0
votes
2
answers
17
UGCNETJuly2018II34
Pushdown automata can recognize language generated by _______ Only context free grammar Only regular grammar Context free grammar or regular grammar Only context sensitive grammar
asked
Jul 13
in
Theory of Computation
by
Pooja Khatri
Active
(
4.3k
points)

46
views
ugcnetjuly2018ii
theoryofcomputation
pushdownautomata
0
votes
1
answer
18
UGC NET JULY 2018 Q34
asked
Jul 11
in
Theory of Computation
by
Sanjay Sharma
Boss
(
49.4k
points)

103
views
push
down
pushdownautomata
0
votes
0
answers
19
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.6k
points)

57
views
pushdownautomata
theoryofcomputation
+3
votes
1
answer
20
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
(
98.5k
points)

200
views
theoryofcomputation
dcfl
contextfreelanguages
pushdownautomata
+1
vote
0
answers
21
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
(
469
points)

33
views
theoryofcomputation
pushdownautomata
0
votes
1
answer
22
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
(
275
points)

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

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

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

97
views
theoryofcomputation
contextfreegrammars
pushdownautomata
+2
votes
1
answer
26
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
(
7.7k
points)

47
views
theoryofcomputation
pushdownautomata
dpda
npda
+4
votes
0
answers
27
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)

48
views
theoryofcomputation
turingmachine
pushdownautomata
finiteautomata
0
votes
0
answers
28
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.9k
points)

120
views
pushdownautomata
npda
theoryofcomputation
+1
vote
3
answers
29
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)

114
views
theoryofcomputation
contextfreelanguage
pushdownautomata
dcfl
contextfreelanguages
+1
vote
2
answers
30
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)

102
views
dcfl
pushdownautomata
contextfreelanguages
Page:
1
2
3
4
5
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
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
Follow @csegate
Gatecse
Recent questions tagged pushdownautomata
Recent Blog Comments
Nice 2 know. You are welcome. :)
Hello @Arjun, I got books now...thanks for your...
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
40,976
questions
47,609
answers
146,779
comments
62,342
users