Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged pushdown-automata
0
votes
0
answers
31
Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more powerful (recognize a larger class of languages) than ... $3-PDAs$ are not more powerful than $2-PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
268
views
michael-sipser
theory-of-computation
pushdown-automata
finite-automata
descriptive
1
vote
0
answers
32
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$.
admin
asked
in
Theory of Computation
Oct 12, 2019
by
admin
780
views
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
descriptive
0
votes
0
answers
33
Peter Linz Edition 4 Exercise 7.2 Question 18 (Page No. 196)
Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1. Theorem 7.1: For any context-free language L, there exists an npda M such that L = L (M).
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
384
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
34
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 context-free language.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
298
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
35
Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
Find a context-free 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,λ)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
315
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
36
Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
286
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
37
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. 191-193) Example 7.8 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
399
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
1
answer
38
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
476
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
2
answers
39
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
1.4k
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
40
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
213
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
41
Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
258
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
1
answer
42
Peter Linz Edition 4 Exercise 7.2 Question 4 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
301
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
43
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 aSbb|aab$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
193
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
44
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$ }.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
187
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
0
votes
0
answers
45
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 aSbb|a.$
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
199
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
0
votes
0
answers
46
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
716
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
47
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^*)$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
253
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
48
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$}?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
192
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
49
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
233
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
npda
0
votes
0
answers
50
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
217
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
1
answer
51
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?
manisha11
asked
in
Theory of Computation
May 13, 2019
by
manisha11
613
views
pushdown-automata
pushdown-automata
0
votes
0
answers
52
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.}$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
453
views
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
0
answers
53
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.}$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
302
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
0
answers
54
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\}.$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
967
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
1
vote
0
answers
55
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\#x|w^{R}$ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
296
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
0
answers
56
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{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
826
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
1
answer
57
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
512
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
58
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
342
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
59
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.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
359
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
60
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
408
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
Page:
« prev
1
2
3
4
5
6
7
8
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged pushdown-automata
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...