Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged pushdown-automata
8
votes
1
answer
1
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 57
Consider a pushdown automaton (PDA) with two control states $Q=\{q 1, q 2\}$, start state $q 1$, input alphabet $\Sigma=\{a, b\}$, stack alphabet $\Gamma=\{\perp, a\}$ (where $\perp$ is the start symbol ... $21$ accepted by the above pushdown automaton is _________.
Consider a pushdown automaton (PDA) with two control states $Q=\{q 1, q 2\}$, start state $q 1$, input alphabet $\Sigma=\{a, b\}$, stack alphabet $\Gamma=\{\perp, a\}$ (w...
GO Classes
534
views
GO Classes
asked
Jan 28
Theory of Computation
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
pushdown-automata
2-marks
+
–
6
votes
1
answer
2
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 65
Consider the following non-deterministic pushdown automaton. The input alphabet is $\{a, b\}$, the stack alphabet is $\{*, a, b\}$, and the initial stack symbol is $*$. Acceptance is by empty stack. We use $x$ as a variable that ranges over ... and $a, a: a a$ and $a, b: a b$. How many strings of length $12$ are accepted by this NPDA?
Consider the following non-deterministic pushdown automaton. The input alphabet is $\{a, b\}$, the stack alphabet is $\{*, a, b\}$, and the initial stack symbol is $*$. A...
GO Classes
668
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
numerical-answers
theory-of-computation
pushdown-automata
2-marks
+
–
1
votes
1
answer
3
Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?
If it’s DCFL then also construct the DPDA ?
vedantk
133
views
vedantk
asked
Jan 10
Theory of Computation
theory-of-computation
context-free-language
dcfl
identify-class-language
pushdown-automata
+
–
1
votes
0
answers
4
Language to PDA
Design the Push down Automata for the language L={anbmc2nd3m,n,m>=1}.Check the acceptance string by both the empty stack and final state method.
Design the Push down Automata for the language L={anbmc2nd3m,n,m>=1}.Check the acceptance string by both the empty stack and final state method.
alexmurugan
334
views
alexmurugan
asked
Nov 3, 2023
Theory of Computation
theory-of-computation
pushdown-automata
+
–
3
votes
2
answers
5
TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Jiten008
343
views
Jiten008
asked
Oct 24, 2023
Theory of Computation
pushdown-automata
theory-of-computation
self-doubt
regular-language
context-free-language
context-sensitive
turing-machine
closure-property
context-free-grammar
+
–
0
votes
1
answer
6
General Doubt
Convert this language to Push Down Automata – {a^n u | u ∈ {a, b}*, |u| = n, n ≥ 0}
Convert this language to Push Down Automata – {a^n u | u ∈ {a, b}*, |u| = n, n ≥ 0}
Shaina Singh
215
views
Shaina Singh
asked
Jul 31, 2023
Theory of Computation
pushdown-automata
context-free-language
+
–
0
votes
1
answer
7
Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }
Is the following language CFL :{ ww | w in (a+b)* and |w| <1000 }
practicalmetal
528
views
practicalmetal
asked
Mar 20, 2023
Theory of Computation
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
+
–
0
votes
1
answer
8
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.
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
496
views
practicalmetal
asked
Mar 15, 2023
Theory of Computation
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
+
–
12
votes
5
answers
9
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\}$
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\}...
admin
6.8k
views
admin
asked
Feb 15, 2023
Theory of Computation
gatecse-2023
theory-of-computation
pushdown-automata
2-marks
+
–
0
votes
0
answers
10
Context Free Languages(CFG) Push Down Anutomata(PDA)
PDA for $a^i b^j | i \neq 2j+1$ ?
PDA for $a^i b^j | i \neq 2j+1$ ?
jaisyking
187
views
jaisyking
asked
Jan 12, 2023
Theory of Computation
theory-of-computation
context-free-grammar
pushdown-automata
context-free-language
+
–
1
votes
1
answer
11
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}
Construct pushdown automata that recognize the following language.L= (a²ⁿ b³ⁿ | n ≥ 0}
M_Umair_Khan42900
292
views
M_Umair_Khan42900
asked
Dec 29, 2022
Theory of Computation
theory-of-computation
regular-language
pushdown-automata
context-free-language
minimal-state-automata
+
–
1
votes
1
answer
12
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.
Write regular expression to denote a language La) String which begin or end with either 00 or 11.b) The set of all strings, when viewed as binary representation of intege...
M_Umair_Khan42900
2.1k
views
M_Umair_Khan42900
asked
Dec 29, 2022
Theory of Computation
theory-of-computation
regular-expression
finite-automata
pushdown-automata
minimal-state-automata
computer
+
–
2
votes
0
answers
13
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
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 th...
h4kr
280
views
h4kr
asked
Dec 23, 2022
Theory of Computation
theory-of-computation
context-free-language
context-sensitive
pushdown-automata
+
–
0
votes
1
answer
14
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
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 trans...
Souvik33
469
views
Souvik33
asked
Dec 20, 2022
Compiler Design
theory-of-computation
pushdown-automata
context-free-grammar
+
–
1
votes
1
answer
15
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
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 ...
Souvik33
411
views
Souvik33
asked
Nov 26, 2022
Theory of Computation
pushdown-automata
theory-of-computation
context-free-language
+
–
1
votes
1
answer
16
Gate@zeal Test Series 2022
Please explain with simplified diagram the transition in the pda. Ans (d)
Please explain with simplified diagram the transition in the pda. Ans (d)
SKMAKM
304
views
SKMAKM
asked
Jul 18, 2022
Theory of Computation
pushdown-automata
+
–
2
votes
1
answer
17
GO Classes Test Series 2023 | Theory of Computation | Test 3 | Question: 5
The language $\left\{w w \mid w \in(0+1)^{\ast}\right\}$ is not accepted by any Turing machine accepted by some Turing machine, but by no pushdown automaton accepted by some pushdown automaton, but not context-free context-free, but not regular
The language $\left\{w w \mid w \in(0+1)^{\ast}\right\}$ isnot accepted by any Turing machineaccepted by some Turing machine, but by no pushdown automatonaccepted by some...
GO Classes
269
views
GO Classes
asked
Jun 27, 2022
Theory of Computation
goclasses2024-toc-3-weekly-quiz
goclasses
theory-of-computation
pushdown-automata
turing-machine
1-mark
+
–
1
votes
2
answers
18
DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.
Is the following language a DCFL? Please explain your reasoning.
atulcse
676
views
atulcse
asked
Jan 21, 2022
Theory of Computation
theory-of-computation
dcfl
context-free-language
pushdown-automata
+
–
32
votes
2
answers
19
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 ___________
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...
Arjun
10.5k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set1
theory-of-computation
pushdown-automata
numerical-answers
2-marks
+
–
2
votes
2
answers
20
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
Which machine is equally powerful in both deterministic and non-deterministic form?Push Down AutomataTuring machineLinear Bounded AutomataNone of the options
admin
1.6k
views
admin
asked
Mar 30, 2020
Theory of Computation
nielit2017dec-scientistb
pushdown-automata
turing-machine
+
–
1
votes
2
answers
21
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.
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 ...
admin
558
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
+
–
0
votes
0
answers
22
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.
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. For...
admin
481
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
+
–
Page:
1
2
3
4
5
6
...
8
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register