The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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 pushdownautomata
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

64
views
michaelsipser
theoryofcomputation
pushdownautomata
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 4 Question 24 (Page No. 212)
A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.
asked
Oct 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
michaelsipser
theoryofcomputation
pushdownautomata
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $kPDA$ be a pushdown automaton that has $k$ stacks. Thus a $0PDA$ is an $NFA$ and a $1PDA$ is a conventional $PDA$. You already know that $1PDAs$ are more powerful (recognize a larger class of languages) than ... $3PDAs$ are not more powerful than $2PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)
asked
Oct 16, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

17
views
michaelsipser
theoryofcomputation
pushdownautomata
nfadfa
descriptive
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 2 Question 47 (Page No. 159)
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

104
views
michaelsipser
theoryofcomputation
contextfreegrammars
pushdownautomata
descriptive
0
votes
0
answers
5
Peter Linz Edition 4 Exercise 7.2 Question 18 (Page No. 196)
Give a construction by which an arbitrary contextfree grammar can be used in the proof of Theorem 7.1. Theorem 7.1: For any contextfree language L, there exists an npda M such that L = L (M).
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3

22
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 7.2 Question 17 (Page No. 196)
Give full details of the proof of Theorem 7.2 . Theorem 7.2 : If L = L (M) for some npda M, then L is a contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3

31
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
7
Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
Find a contextfree grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions $δ(q_0, a,z) =$ {$(q_0, Az)$}, $δ (q_0,b, A) =$ {$(q_0, AA)$}, $δ(q_0, a, A) =$ {$(q_1,λ)$}.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3

31
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3

36
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 7.2 Question 11,12,13 (Page No. 195)
Show that the npda in Example 7.8 accepts L (aa*b). Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b). show that the variable ($q_0zq_1$) is useless. (see page no. 191193) Example 7.8 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3

28
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
1
answer
10
Peter Linz Edition 4 Exercise 7.2 Question 10 (Page No. 195)
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

60
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
1
answer
11
Peter Linz Edition 4 Exercise 7.2 Question 9 (Page No. 195)
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

117
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 7.2 Question 7,8 (Page No. 195)
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$. Show how the number of states of $\widehat M $ in the above exercise can be reduced to two.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

29
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABBaAA,$ $A\rightarrow aBBa,$ $B\rightarrow bBBA.$
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

27
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 7.2 Question 4 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S → aSSSab$.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

19
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 7.2 Question 3 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbbaab$.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

27
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 7.2 Question 2 (Page No. 195)
Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

27
views
theoryofcomputation
peterlinz
peterlinzedition4
pushdownautomata
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 7.2 Question 1 (Page No. 195)
Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the language generated by the given grammar. Example 7.6: Construct a pda that accepts the language generated by a grammar with productions $S\rightarrow aSbba.$
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

28
views
theoryofcomputation
peterlinz
peterlinzedition4
pushdownautomata
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 7.1 Question 16 (Page No. 184)
We can define a restricted npda as one that can increase the length of the stack by at most one symbol in each move, changing Definition 7.1 so that $\delta :$Q x $(\sum \cup$ {$\lambda$}$) $ ... the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

110
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 7.1 Question 14 (Page No. 184)
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

17
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 7.1 Question 13 (Page No. 184)
What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

11
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 7.1 Question 11 (Page No. 184)
What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) with transitions $\delta(q_0,a,z)=${$(q_1,a),(q_2,\lambda)$}, $\delta(q_1,b,a)=${$(q_1,b)$}, $\delta(q_1,b,b)=${$(q_1,b)$}, $\delta(q_1,a,b)=${$(q_2,\lambda)$} ?
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

17
views
theoryofcomputation
peterlinz
peterlinzedition4
pushdownautomata
npda
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 7.1 Question 10 (Page No. 184)
What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}), with $\delta(q_0,b,z)=${$(q_1,1z)$}, $\delta(q_0,b,1)=${$(q_1,11)$}, $\delta(q_2,a,1)=${$(q_3,\lambda)$}, $\delta(q_3,a,1)=${$(q_4,\lambda)$} $\delta(q_4,a,z)=${$(q_4,z),(q_5,z)$} ?
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3

19
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
+1
vote
0
answers
23
pda self doubt
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack. DPDA with empty stack accepts LR(0) grammar. Can someone explain in depth/or give good reference links?
asked
May 13, 2019
in
Theory of Computation
by
manisha11

67
views
pushdownautomata
pushdownautomata
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 2 Question 12 (Page No. 156)
Convert the $CFG$ $G$ $R\rightarrow XRX \mid S$ $S\rightarrow aT b \mid bT a$ $T\rightarrow XT X \mid X \mid\epsilon$ $X\rightarrow a \mid b$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
asked
May 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

51
views
michaelsipser
theoryofcomputation
contextfreegrammars
pushdownautomata
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 2 Question 11 (Page No. 155)
Convert the $CFG$ $G_{4}$ $E\rightarrow E+T\mid T$ $T\rightarrow T\times F\mid F$ $F\rightarrow (E)\mid a$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
asked
May 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 2 Question 10 (Page No. 155)
Give an informal description of a pushdown automaton that recognizes the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$
asked
May 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

73
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 2 Question 7 (Page No. 155)
Give informal English descriptions of PDAs for the following languages. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$ The complement of the language $\{a^{n}b^{n}n\geq 0\}$ $\{w\#xw^{R}$ $\text{is a substring of $ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
asked
May 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

34
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 2 Question 5 (Page No. 155)
Give informal descriptions and state diagrams of pushdown automata for the languages in the following languages In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w w contains at least three 1's}}$ ... $\text{{$ww=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
asked
May 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

75
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3

56
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 7.1 Question 8 (Page No. 183)
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3

63
views
peterlinz
peterlinzedition4
theoryofcomputation
pushdownautomata
npda
Page:
1
2
3
4
5
6
7
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
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
IIT Tirupati MS Interview 2020
IIT Bombay Mtech RA  interview experience (2020)
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged pushdownautomata
Recent Blog Comments
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
ISI 2019 : Aarushi Aiyyar's answer to How do...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,484
answers
201,816
comments
95,291
users