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
1
answer
1
Autometa | PDA
Consider the following Language: L= $a^{n}b^{n}c^{n}$ | $n \geq 0$ Consider the following Statement: A PDA can accept the given language. As we can insert 2 a’s for every entry of a, and pop one ‘a’ for every b and after all b’s, pop one ‘a’ for every entry of ‘c’ So the above language is a CFL. Prove the above statement WRONG
Souvik33
asked
in
Theory of Computation
9 hours
ago
by
Souvik33
35
views
pushdown-automata
theory-of-computation
context-free-language
0
votes
1
answer
2
[email protected]
Test Series 2022
Please explain with simplified diagram the transition in the pda. Ans (d)
Amit Mehta
asked
in
Theory of Computation
Jul 18
by
Amit Mehta
131
views
pushdown-automata
1
vote
2
answers
3
DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.
atulcse
asked
in
Theory of Computation
Jan 21
by
atulcse
344
views
theory-of-computation
dcfl
context-free-language
pushdown-automata
16
votes
2
answers
4
GATE CSE 2021 Set 1 | Question: 51
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$ ... $\Gamma = \{ \#, A\}$. The number of strings of length $100$ accepted by the above pushdown automaton is ___________
Arjun
asked
in
Theory of Computation
Feb 18, 2021
by
Arjun
5.3k
views
gatecse-2021-set1
theory-of-computation
pushdown-automata
numerical-answers
2
votes
2
answers
5
NIELIT 2017 DEC Scientist B - Section B: 57
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
1.0k
views
nielit2017dec-scientistb
pushdown-automata
turing-machine
1
vote
2
answers
6
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.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Patel RJIT
401
views
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
0
votes
0
answers
7
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.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 17, 2019
by
Lakshman Patel RJIT
306
views
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
0
votes
0
answers
8
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.)
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 15, 2019
by
Lakshman Patel RJIT
178
views
michael-sipser
theory-of-computation
pushdown-automata
finite-automata
descriptive
1
vote
0
answers
9
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$.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 13, 2019
by
Lakshman Patel RJIT
614
views
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
descriptive
0
votes
0
answers
10
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
198
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
11
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
197
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
12
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
220
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
13
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
205
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
14
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
238
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
1
answer
15
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
293
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
2
answers
16
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
915
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
17
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
164
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
18
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
167
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
1
answer
19
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
215
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
20
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
141
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
21
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
121
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
0
votes
0
answers
22
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
148
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
0
votes
0
answers
23
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
533
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
24
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
190
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
25
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
121
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
Page:
1
2
3
4
5
6
7
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
RECRUITMENT IN OIL AND GAS CORPORATION LIMITED
Aptitude Overflow Book
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(647)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(854)
Recent questions tagged pushdown-automata
Recent Blog Comments
@abir_banerjee Thanks Abir. I'm third year...
@nolan_keats Currently I am in third year...
@abir_banerjee thank you Abir.Supposing you...
@nolan_keats just a suggestion as I also...
@abir_banerjee Hope I can do this in span of one...