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 npda
0
votes
1
answer
1
TESTBOOK TEST SERIES
WHAT WILL BE THE ANS?
asked
Oct 3, 2018
in
Theory of Computation
by
Avik Chowdhury
Junior
(
883
points)

40
views
npda
0
votes
0
answers
2
Existence of a 2 state NPDA
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
asked
Jul 15, 2018
in
Theory of Computation
by
Lakshay Kakkar
Active
(
2k
points)

26
views
peterlinz
theoryofcomputation
npda
+1
vote
2
answers
3
#Test series
Q. {al bm cn  l ≠ m or m ≠ n} construct a PDA for this language?
asked
Jul 10, 2018
in
Theory of Computation
by
himgta
Active
(
3.2k
points)

43
views
npda
0
votes
1
answer
4
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
(
159
points)

68
views
theoryofcomputation
dpda
npda
+4
votes
0
answers
5
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
(
159
points)

171
views
theoryofcomputation
npda
dpda
0
votes
0
answers
6
Construct a NPDA (peter linz) Exercise 7.2.6
Construct a NPDA corresponding to the grammar. $S \rightarrow AAa$ $A\rightarrow SAb$ also convert the given grammar to GNF.
asked
Mar 25, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
32.8k
points)

165
views
theoryofcomputation
peterlinz
pushdownautomata
npda
+2
votes
1
answer
7
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
Loyal
(
8.8k
points)

60
views
theoryofcomputation
pushdownautomata
dpda
npda
0
votes
0
answers
8
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
(
18.2k
points)

143
views
pushdownautomata
npda
theoryofcomputation
+1
vote
2
answers
9
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
(
897
points)

236
views
theoryofcomputation
pushdownautomata
dpda
npda
+1
vote
0
answers
10
made easy test series
The language {w the length of w is odd and it's middle symbol is 0, Wε(0+1)*} Why do we need a PDA for above language. I don't think we need a PDA for this language. I wrote the following RE. Tell me whats wrong in it: [(0+1)(0+1)(0+1)]+0[(0+1)(0+1)(0+1)]+ + (other small left over strings like 0,101,100,001,000..... which are not covered in first part of expression)
asked
Nov 29, 2017
in
Theory of Computation
by
♥_Less
Active
(
1k
points)

96
views
madeeasytestseries
theoryofcomputation
dpda
npda
cfg
regularexpressions
regularlanguages
0
votes
0
answers
11
Practice question #4
Consider the machines, M1  a NPDA accepting L1, M2  a 2 way PDA accepting L2, M3  a PDA with two stacks accepting L3. Choose the false statement, 1) For any CFL L, there exists some M1, M2 and M3. 2) For some CSL L, there exists some M1,M2 and M3. 3) For every recursive set, there exists some M1,M2 and M3. 4) The power of the machines are not M1 <= M2 < M3.
asked
Sep 18, 2017
in
Theory of Computation
by
AnilGoudar
Active
(
4.7k
points)

87
views
theoryofcomputation
npda
+1
vote
1
answer
12
TOC DPDA vs NPDA
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant. Assume i have a language ,over alphabet a,b,c,dL=( W n(a)=n(b) and n(c)=n(d) ),where n(a) is number if a in words. It is a CFL. Now can DPA handle this ?If yes,then how?If not,then why?
asked
Jul 31, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
26.5k
points)

644
views
pushdownautomata
npda
theoryofcomputation
contextfreelanguage
deterministiccontextfreegrammars
+1
vote
1
answer
13
Peter Linz Exercise 7.1
Q1) Given, $L1 = (aaa^*b)$ $L2 = (aab^*aba^*)$ Find the union of $L1$ and $L2$, and also find $L1  L2$. Q2) Find the npda's of the following: 1) $L = \{ a^nb^m :n \leq m \leq 3n\}$ 2) $L = \{w : 2n_a(w) \leq n_b(w)) \leq 3n_a(w) \}$.
asked
Jul 8, 2017
in
Theory of Computation
by
Shubhanshu
Boss
(
17.8k
points)

164
views
theoryofcomputation
contextfreelanguage
peterlinz
pushdownautomata
npda
pushdownautomata
0
votes
1
answer
14
NPDA and DPDA
Can we make NPDA? L= {anbn n>=0,a,b are input variables} if yes then make it .
asked
Jul 6, 2017
in
Theory of Computation
by
akankshadewangan24
Active
(
4.3k
points)

349
views
pushdownautomata
npda
+3
votes
1
answer
15
How to construct npda for given languages (Peter Linz 3rd Ed, Exercise 7, Ques 4)?
asked
Apr 30, 2017
in
Theory of Computation
by
Vishal Goel
Active
(
1.7k
points)

305
views
pushdownautomata
theoryofcomputation
npda
nondeterminism
peterlinz
contextfreelanguages
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
How to Revise?
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
GATE like Virtual Calculator for GateOverflow  A Chrome extension
Follow @csegate
Gatecse
Recent questions tagged npda
Recent Blog Comments
yes im also going through same phase ....5...6 ...
46,668
questions
51,139
answers
176,296
comments
66,556
users