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
Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }
practicalmetal
asked
in
Theory of Computation
Mar 21
by
practicalmetal
178
views
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
1
answer
2
Context Free Languages
Is the following language context free: The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.
practicalmetal
asked
in
Theory of Computation
Mar 16
by
practicalmetal
175
views
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
2
votes
2
answers
3
GATE CSE 2023 | Question: 30
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ ... $\left.0 \leq n\right\}$ $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$
admin
asked
in
Theory of Computation
Feb 15
by
admin
1.3k
views
gatecse-2023
theory-of-computation
pushdown-automata
2-marks
0
votes
0
answers
4
Context Free Languages(CFG) Push Down Anutomata(PDA)
PDA for $a^i b^j | i \neq 2j+1$ ?
jaisyking
asked
in
Theory of Computation
Jan 12
by
jaisyking
63
views
theory-of-computation
context-free-grammar
pushdown-automata
context-free-language
0
votes
1
answer
5
Construct pushdown automata that recognize the following language. L= (a²ⁿ b³ⁿ | n ≥ 0}
Construct pushdown automata that recognize the following language. L= (a²ⁿ b³ⁿ | n ≥ 0}
M_Umair_Khan42900
asked
in
Theory of Computation
Dec 29, 2022
by
M_Umair_Khan42900
113
views
theory-of-computation
regular-language
pushdown-automata
context-free-language
minimal-state-automata
0
votes
1
answer
6
Write regular expression to denote a language L a) String which begin or end with either 00 or 11. b) The set of all strings, when viewed as binary representation of integers, that are divisible by 2. c) The set of all strings containing 00. d) String not containing the substring 110.
M_Umair_Khan42900
asked
in
Theory of Computation
Dec 29, 2022
by
M_Umair_Khan42900
394
views
theory-of-computation
regular-expression
finite-automata
pushdown-automata
minimal-state-automata
computer
2
votes
0
answers
7
Is it CFL or CSL?
Is {$a^nb^nc^n$ | $n>=0$} CSL? After comparing both a and b, stack would be empty. So it can’t be CFL. So it is CSL or recursive. And does this language require more than 1 stack? Please tell how would check for the grammer of this language even if it is in CSL. Thank you
h4kr
asked
in
Theory of Computation
Dec 23, 2022
by
h4kr
116
views
theory-of-computation
context-free-language
context-sensitive
pushdown-automata
0
votes
1
answer
8
Push Down Automation | Parsing | Input Buffer and Stack
Consider a situation, where the input buffer is still having elements, and our PDA has reached final state. Given that for next input element the final state has no transition defined. In above situation will the i/p string be ... in all cases May be accepted if empty stack acceptance is allowed in the given PDA Something else, I can explain
Souvik33
asked
in
Compiler Design
Dec 20, 2022
by
Souvik33
125
views
theory-of-computation
pushdown-automata
context-free-grammar
1
vote
1
answer
9
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
Nov 26, 2022
by
Souvik33
197
views
pushdown-automata
theory-of-computation
context-free-language
0
votes
1
answer
10
[email protected]
Test Series 2022
Please explain with simplified diagram the transition in the pda. Ans (d)
SKMAKM
asked
in
Theory of Computation
Jul 18, 2022
by
SKMAKM
183
views
pushdown-automata
1
vote
2
answers
11
DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.
atulcse
asked
in
Theory of Computation
Jan 21, 2022
by
atulcse
449
views
theory-of-computation
dcfl
context-free-language
pushdown-automata
19
votes
2
answers
12
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
6.9k
views
gatecse-2021-set1
theory-of-computation
pushdown-automata
numerical-answers
2-marks
2
votes
2
answers
13
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 Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
1.2k
views
nielit2017dec-scientistb
pushdown-automata
turing-machine
1
vote
2
answers
14
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 Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
435
views
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
0
votes
0
answers
15
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 Bhaiya
asked
in
Theory of Computation
Oct 17, 2019
by
Lakshman Bhaiya
357
views
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
0
votes
0
answers
16
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 Bhaiya
asked
in
Theory of Computation
Oct 15, 2019
by
Lakshman Bhaiya
214
views
michael-sipser
theory-of-computation
pushdown-automata
finite-automata
descriptive
1
vote
0
answers
17
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 Bhaiya
asked
in
Theory of Computation
Oct 13, 2019
by
Lakshman Bhaiya
642
views
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
descriptive
0
votes
0
answers
18
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
248
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
19
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
233
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 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
244
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 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
236
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
22
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
306
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
1
answer
23
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
339
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
Page:
1
2
3
4
5
6
...
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
DRDO Scientist -B
ISRO Scientist-B 2023
BARC RECRUITMENT 2023
COAP Responses | GATE CSE 2023
Interview Experience : M.Tech AI at IIT Jodhpur, Self Sponsored
Subjects
All categories
General Aptitude
(2.8k)
Engineering Mathematics
(9.7k)
Digital Logic
(3.4k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.4k)
Others
(2.4k)
Admissions
(665)
Exam Queries
(1.0k)
Tier 1 Placement Questions
(17)
Job Queries
(77)
Projects
(9)
Unknown Category
(867)
Recent questions tagged pushdown-automata
Recent Blog Comments
@Shubham Sharma 2 Is it possible to get a...
are MSc.(CS) students eligible?
It is said that the gate score will have 80%...
Maybe we should raise our concern in Supreme...
Mtech(RA) CSE 2023 IIT Bombay project 14. Does...