The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
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
Let P be a nondeterministic pushdown automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation ... L(P) is not necessarily ∑* Both L(P) and N(P) is necessarily ∑* Neither L(P) nor N(P) are necessarily ∑*
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
149
points)

10
views
pushdownautomata
theoryofcomputation
0
votes
1
answer
2
Cfg to and from pda
Do i have to study the conversation of pda to Cfg or cfg to pda? Is this an important concept with relevance to gate? I know how to individually make them though.
asked
Jan 21
in
Theory of Computation
by
Rhythm
(
75
points)

29
views
contextfreelanguage
pushdownautomata
0
votes
0
answers
3
Push down automata
asked
Jan 19
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

29
views
theoryofcomputation
pushdownautomata
acetestseries
0
votes
0
answers
4
Building a pushdown automata that receives L*
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it
asked
Jan 16
in
Theory of Computation
by
agmund
(
7
points)

21
views
pushdownautomata
theoryofcomputation
contextfreelanguage
0
votes
0
answers
5
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
(
9
points)

28
views
theoryofcomputation
pushdownautomata
dpda
0
votes
0
answers
6
Draw PDA for this
L = {a^m b^n c^k=m+n }  m >= 0 and n >= 0  Please draw PDA for this Language!
asked
Dec 12, 2018
in
Theory of Computation
by
Guilherme Zanini Mor
(
9
points)

49
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dcfl
0
votes
0
answers
7
pda doubt
Consider the following PDA: The language accepted by the given PDA is: L = {(b^n a b^n a )^m  m, n >= 0} L = {b^n a b^n a  n >= 0} {bn  n >= 0} L = {b^n a b^n a  n >= 0} L = {(b^n a b^n a )^m  m, n >= 0} {bn  n >= 0}
asked
Dec 10, 2018
in
Theory of Computation
by
Satbir
Active
(
5.1k
points)

40
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
8
PDA toc
Plz tell me answer of the below question In automaton theory ,a PDA is a variation of: 1)finite automaton that can make use of a stack containing data 2)infinite automaton that can make use of a stack containing data 3)both A and B 4)none of the above
asked
Dec 8, 2018
in
Theory of Computation
by
Shivshankar
(
41
points)

49
views
pushdownautomata
0
votes
0
answers
9
TOC  PDA
Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z0, X}, where z0 is the bottom of stack marker. The set of states of PDA is {q0,q1} where q0 is the start state and rules of the PDA are, (The languare accepted by the grammar is)
asked
Nov 30, 2018
in
Theory of Computation
by
rahuljai
(
437
points)

58
views
pushdownautomata
theoryofcomputation
contextfreelanguage
grammar
cfg
0
votes
0
answers
10
How to draw PDA For following language
asked
Nov 26, 2018
in
Theory of Computation
by
radha gogia
Loyal
(
8k
points)

39
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
11
Important doubt in TOC
Can someone please explain how and what above PDA is computing
asked
Nov 17, 2018
in
Theory of Computation
by
Pavan Shetty
(
87
points)

17
views
theoryofcomputation
pushdownautomata
0
votes
1
answer
12
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
Active
(
3.9k
points)

44
views
theoryofcomputation
pushdownautomata
dpda
contextfreegrammars
0
votes
2
answers
13
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.3k
points)

84
views
theoryofcomputation
pushdownautomata
dpda
0
votes
0
answers
14
Ace Book
The complement of the language L containing an equal number of a's , b's and c's is a)regular b)context free c)context sensitive but not context free d)recursive and not a CFL
asked
Oct 21, 2018
in
Theory of Computation
by
abhishek1995_cse
(
169
points)

39
views
contextfreelanguage
pushdownautomata
contextsensitive
0
votes
0
answers
15
Pushdown Automata
asked
Oct 19, 2018
in
Theory of Computation
by
Sambhrant Maurya
Active
(
1.5k
points)

67
views
pushdownautomata
theoryofcomputation
dpda
0
votes
0
answers
16
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
Oct 18, 2018
in
Theory of Computation
by
Sambhrant Maurya
Active
(
1.5k
points)

40
views
theoryofcomputation
contextfreegrammars
contextfreelanguage
cfg
pushdownautomata
0
votes
0
answers
17
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, 2018
in
Theory of Computation
by
srestha
Veteran
(
108k
points)

188
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
18
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, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.1k
points)

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

46
views
pushdownautomata
+1
vote
0
answers
20
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, 2018
in
Theory of Computation
by
sushmita
Boss
(
16.8k
points)

16
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
21
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, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

68
views
theoryofcomputation
pushdownautomata
0
votes
0
answers
22
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, 2018
in
Theory of Computation
by
sushmita
Boss
(
16.8k
points)

57
views
theoryofcomputation
contextfreelanguage
pushdownautomata
0
votes
0
answers
23
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, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

66
views
theoryofcomputation
pushdownautomata
0
votes
1
answer
24
PDADoubt
what is the DPDA for L=$a^{2n+1}b^n$  n>1
asked
Sep 3, 2018
in
Theory of Computation
by
aditi19
Active
(
2.3k
points)

145
views
pushdownautomata
0
votes
0
answers
25
PDADoubt
L=$a^mb^n$  m!=n is the following DPDA correct for the mentioned language?
asked
Sep 3, 2018
in
Theory of Computation
by
aditi19
Active
(
2.3k
points)

27
views
pushdownautomata
contextfreelanguage
0
votes
0
answers
26
DoubtPDA
what is the PDA for {L=$a^mb^n$ m>n}
asked
Sep 2, 2018
in
Theory of Computation
by
aditi19
Active
(
2.3k
points)

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

49
views
compilerdesign
parsing
contextfreelanguage
pushdownautomata
theoryofcomputation
0
votes
1
answer
28
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, 2018
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
2.2k
points)

44
views
testbooktestseries
theoryofcomputation
pushdownautomata
0
votes
0
answers
29
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
(
85
points)

148
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dpda
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
Need suggestions for what to do next after Gate ??
For GATECSE Admissions 2019
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
Follow @csegate
Recent questions tagged pushdownautomata
Recent Blog Comments
Well it is quite nostalgic for me as if I have...
See in recent posts "For GATE CSE Admissions 2019"
which ppt are you referring to, can you share the...
I am not a ranker so you might not believe on my...
What is the status on appsgate website? I...
47,932
questions
52,335
answers
182,384
comments
67,817
users