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
+1
vote
0
answers
1
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
in
Theory of Computation
by
manisha11
Active
(
2.1k
points)

26
views
pushdownautomata
pushdownautomata
0
votes
0
answers
2
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

13
views
michaelsipser
theoryofcomputation
contextfreegrammars
pushdownautomata
0
votes
0
answers
3
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 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
4
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 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
5
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 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

11
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
6
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 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

18
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
7
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

27
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
8
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

23
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 7.1 Question 7 (Page No. 183)
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

21
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 7.1 Question 6 (Page No. 183)
Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

22
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 7.1 Question 5 (Page No. 183)
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

14
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 7.1 Question 4 (Page No. 183)
Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}. (a) $L =$ {$a^nb^{2n} : n ≥ 0$}. (b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}. (c) $L =$ {$a^nb^mc^{n+m} : n ≥ 0, m ≥ 0$}. (d) $L =$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

15
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 7.1 Question 3 (Page No. 183)
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

25
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 7.1 Question 2 (Page No. 183)
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

18
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 7.1 Question 1 (Page No. 183)
Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.
asked
Apr 20
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

26
views
peterlinz
theoryofcomputation
pushdownautomata
0
votes
0
answers
16
Ullman (TOC) Edition 3 Exercise 6.4 Question 4 (Page No. 257)
Show that the language $L=\{0^{n}1^{n}n\geq 1\}\cup \{0^{n}1^{2n}n\geq 1\}$ is a contextfree language that is not accepted by any $DPDA$ Hint$:$ Show that there must be two strings of the form $0^{n}1^{n}$ for ... Thus the $DPDA$ cannot tell whether or not to accept next after seeing $n_{1}$ $1's$ or after seeing $n_{2}$ $1's.$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

16
views
ullman
theoryofcomputation
pushdownautomata
contextfreelanguages
0
votes
0
answers
17
Ullman (TOC) Edition 3 Exercise 6.4 Question 3 (Page No. 257)
We can prove Theorem $6.19$ in three parts$:$ Show that if $L=N(P)$ for some $DPDA$ $P,$ then $L$ has the prefix property. Show that if $L=N(P)$ for some $DPDA$ $P,$ then there exists a $DPDA$ $P'$ such that $L=L(P').$ Show ... has the prefix property and is $L(P')$ for some $DPDA$ $P',$ then there exists a $DPDA$ $P$ such that $L=N(P).$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

27
views
ullman
theoryofcomputation
pushdownautomata
contextfreelanguages
0
votes
0
answers
18
Ullman (TOC) Edition 3 Exercise 6.4 Question 2 (Page No. 256  257)
Give deterministic pushdown automata to accept the following languages$:$ $\{0^{n}1^{m}n\leq m\}$ $\{0^{n}1^{m}n\geq m\}$ $\text{\{$0^{n}1^{m}0^{n}$n and m are arbitrary\}}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

17
views
ullman
theoryofcomputation
pushdownautomata
contextfreelanguages
0
votes
0
answers
19
Ullman (TOC) Edition 3 Exercise 6.4 Question 1 (Page No. 256)
For each of the following PDA's, tell whether or not it is deterministic. Either show that it meets the definition of a DPDA or find a rule or rules that violate it. $a)$ $b)$ Suppose the $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ ... $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

12
views
ullman
theoryofcomputation
pushdownautomata
contextfreegrammars
0
votes
0
answers
20
Ullman (TOC) Edition 3 Exercise 6.3 Question 7 (Page No. 252)
Suppose we have a PDA with $s$ states $t$ stack symbols and no rule in which a replacement stack string has a length greater than $u.$ Give a tight upper bound on the number of variables in the $CFG$ that we construct for this PDA by the method of an empty stack.
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

8
views
ullman
theoryofcomputation
pushdownautomata
contextfreegrammars
0
votes
0
answers
21
Ullman (TOC) Edition 3 Exercise 6.3 Question 6 (Page No. 252)
Show that if $P$ is a PDA, then there is a onestate PDA $,P_{1},$ such that $N(P_{1})=N(P).$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

4
views
ullman
theoryofcomputation
pushdownautomata
0
votes
0
answers
22
Ullman (TOC) Edition 3 Exercise 6.3 Question 5 (Page No. 252)
Below are some contextfree languages.For each,devise a PDA that accepts the language by empty stack. You may ,if you wish, first construct a grammar for the language, and then convert to a $PDA:$ $\{a^{n}b^{m}c^{2(n+m)}n\geq 0,m\geq 0\}$ $\{a^{i}b^{j}c^{k}i=2j $(or)$ j=2k\}$ $\{0^{n}1^{m}n\leq m\leq 2n\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

12
views
ullman
theoryofcomputation
contextfreegrammars
pushdownautomata
0
votes
0
answers
23
Ullman (TOC) Edition 3 Exercise 6.3 Question 4 (Page No. 252)
Convert the $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ to a $CFG,$ if $\delta$ given by $:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ $\delta(q,\in,X)=\{p,\in\}$ $\delta(p,\in,X)=\{p,\in\}$ $\delta(p,1,X)=\{(p,XX)\}$ $\delta(p,1,Z_{0})=\{p,\in\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

5
views
ullman
theoryofcomputation
pushdownautomata
contextfreegrammars
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 6.3 Question 3 (Page No. 251)
Convert the $PDA$ $P=(\{p,q\},\{0,1\},\{X,Z_{0}\},\delta.q.Z_{0})$ to a $CFG,$ if $\delta$ is given by $:$ $\delta(q,1,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,1,X)=\{(q,XX)\}$ $\delta(q,0,X)=\{(p,X)\}$ $\delta(q,\in,X)=\{(q,\in)\}$ $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

5
views
ullman
pushdownautomata
contextfreegrammars
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 6.3 Question 2 (Page No. 251)
Convert the grammar $S\rightarrow aAA$ $A\rightarrow aSbSa$ to a PDA that accepts the same language by empty stack.
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

5
views
ullman
theoryofcomputation
pushdownautomata
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 6.3 Question 1 (Page No. 251)
Convert the grammar $S\rightarrow 0S1A$ $A\rightarrow 1A0S\in$ to a PDA that accepts the same language by empty stack.
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

7
views
ullman
theoryofcomputation
pushdownautomata
0
votes
1
answer
27
Vani institute question bank
5. For n ≥ 0, Ln = {a^i b^k  i ≥ n, 0 < k < i} (a) Ln is regular, independent of value of n (b) Ln is not regular, independent of value of n (c) Ln is regular only for small value of n (d) None of above
asked
Apr 7
in
Theory of Computation
by
Hirak
Active
(
1.7k
points)

13
views
theoryofcomputation
pushdownautomata
finiteautomata
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 6.2 Question 8 (Page No. 242)
A $PDA$ is called restricted if on any transition it can increase the height of the stack by at most one symbol.That is for any rule $\delta(q,a,Z)$ contains $(p,\gamma),$ it must be that $\gamma\leq 2.$ Show that if $P$ is a $PDA,$then there is a restricted $PDA$ $P_{3},$such that $L(P)=L(P_{3}).$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

12
views
ullman
theoryofcomputation
pushdownautomata
descriptive
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 6.2 Question 7 (Page No. 242)
How that if $P$ is a $PDA,$ then there is a $PDA$ $P_{2}$ with only two stack symbols such that $L(P_{2}=L(P).$ Hint$:$ Binarycode the stack alphabet of $P$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

7
views
ullman
theoryofcomputation
pushdownautomata
descriptive
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 6.2 Question 6 (Page No. 242)
Suppose th $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ has the following transition function$:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ ... $PDA$ $P_{2}$ such that $L(P_{2})=N(P)$ i.e., $P_{2}$ accepts by final state what $P$ accepts by empty stack.
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

10
views
ullman
theoryofcomputation
pushdownautomata
descriptive
Page:
1
2
3
4
5
6
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
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
Follow @csegate
Recent questions tagged pushdownautomata
Recent Blog Comments
@kunal If you were in Software Lab 2, then you...
No such thing was mentioned to us. There was no...
C and C++ were allowed (Compiler was g++ ). Only...
49,403
questions
53,576
answers
185,762
comments
70,852
users