Register

Recent questions tagged pushdown-automata

0 0 votes
0 0 answers
1.4k
1.4k views
Pushdown Automata
User Avatar
2 2 votes
2 2 answers
1.5k
1.5k views
Context Free Grammar
Consider the following CFG 'G'S aA/bSS/SSA aAb/bAa/AA/εThe language generated by G is:a)Set of all strings with atleast one 'a'b)Set of all strings with atleast two a's...
User Avatar
0 0 votes
0 0 answers
1.9k
1.9k views
CFL with Empty Stack or Final State
$1)$"We can solve same PDA with empty stack and using final state"Can give an example of such language? Where is the difference between solving a pda with empty stak and ...
User Avatar
0 0 votes
0 0 answers
304
304 views
Self doubt Pushdown Automata
Is it required to initialize stack symbol in PDA?If yes then does this PDA have valid transitions?
User Avatar
0 0 votes
1 1 answer
1.9k
1.9k views
Testbook Test Series: Theory of Computation - Pushdown Automata
$\overline{L(M)}$ isRegular DCFL but not regularCFL but not DCFLRecursive but not CFL
User Avatar
0 0 votes
1 1 answer
761
761 views
Pushdown automata
L={ai bj | i ≠ 2j+1}please give PDA for this language
User Avatar
1 1 vote
0 0 answers
751
751 views
Michael sipser
I read this excerpt from sipser book-We write “a,b → c” to signify that when the machine is reading ana from the input, it may replace the symbol b on the top of the stac...
User Avatar
0 0 votes
0 0 answers
1.5k
1.5k views
Push down automata
Consider following PDA WHICH OF FOLLOWING IS TRUE ABOUT LANGUAGE ACCEPTED BY IT ?A. Regular but infiniteB. Regular but finiteC. DCFL but not regularD. CFL but not DCFL
User Avatar
0 0 votes
0 0 answers
1.7k
1.7k views
self doubt
Consider the Context free language which has equal no of as and bs. eg- ababSince a proper prefix ab also belongs to this language, this language does not satisfy prefix...
User Avatar
0 0 votes
0 0 answers
1.8k
1.8k views
Push Down Automata
Consider A given PDA as following Qo is the start state here. What is the language accepted by the given PDA ?1. { ( bn a bn a )m | m,n ≥ 0 }2. { ( bn a bn a )m | m,n ≥ ...
User Avatar
1 1 vote
1 answers 1 answer
3.9k
3.9k views
PDA-Doubt
what is the DPDA for L=$a^{2n+1}b^n$ | n>1
User Avatar
0 0 votes
0 0 answers
570
570 views
PDA-Doubt
L=$a^mb^n$ | m!=nis the following DPDA correct for the mentioned language?
User Avatar
0 0 votes
0 0 answers
2.6k
2.6k views
Doubt-PDA
what is the PDA for {L=$a^mb^n$ |m>n}
User Avatar
0 0 votes
1 1 answer
934
934 views
Parsing
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?
User Avatar
1 1 vote
0 0 answers
2.5k
2.5k views
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ?I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
User Avatar
0 0 votes
6 6 answers
4.3k
4.3k views
UGC NET CSE | July 2018 | Part 2 | Question: 33
A pushdown automata behaves like a Turing machine when the number of auxiliary memory is011 or more2 or more
User Avatar
0 0 votes
3 3 answers
3.9k
3.9k views
UGC NET CSE | July 2018 | Part 2 | Question: 34
Pushdown automata can recognize language generated by _______Only context free grammarOnly regular grammarContext free grammar or regular grammarOnly context sensitive gr...
User Avatar
0 0 votes
0 0 answers
1.5k
1.5k views
PDA Doubt
Please can anyone explain the PDA for reverse of a string via a transition graph
User Avatar
4 4 votes
2 2 answers
3.6k
3.6k views
DCFL or Not
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$Which one DCFL...
User Avatar
1 1 vote
0 0 answers
409
409 views
Pda Automata
Why only stack data structure is used for implementing pushdown automata(pda) why not others ???
User Avatar
0 0 votes
1 1 answer
1.6k
1.6k views
PDA for a language
$a^i b^j / i$ should not be equal to $2j+1$give PDA for this language
User Avatar
0 0 votes
1 1 answer
783
783 views
pushdown-automata
User Avatar
0 0 votes
0 0 answers
1.1k
1.1k views
Peter Linz Edition 4 Exercise 7.2 Question 6 (Page No. 195)
Construct a NPDA corresponding to the grammar.$S \rightarrow AA|a$$A\rightarrow SA|b$also convert the given grammar to GNF.
User Avatar
0 0 votes
1 1 answer
993
993 views
Context free grammar and push down automata.
Is true..? In an unambiguous grammar every string has exactly one derivation.
User Avatar
3 3 votes
1 1 answer
1.0k
1.0k views
Power of Pushdown Machines
Which is more powerful :- 2-way Non-Deterministic Pushdown Machine(NDPDM) or 2-way Deterministic Pushdown Machine(DPDM) ? (or) Do both machine models have the same power ...
User Avatar
0 0 votes
2 2 answers
807
807 views
Uttrakhand Asst. Professor Exam-76
Statement 1 : For push down automata Determinism ≠ Non-determinismStatement 2 : For Finite Automata Non-determinism = DeterminismWhich of the following is correct?Both st...
User Avatar
3 3 votes
0 0 answers
2.9k
2.9k views
Self doubt
Which of the following statement TRUE & also EXPLAIN WHY...(1) "Power of Turing Machine is Equal to Power of DFA with 2 Stack"(2) "Power of Turing Machine is Equal to Pow...
User Avatar
0 0 votes
0 0 answers
1.7k
1.7k views
Non-Deterministic PDA
I'm getting its equaltion {anbn | n 0} U {a} U {b}But given is {anbn | n >= 0} U {a} U {b}Whether epsilon is accepted or not??
User Avatar
2 2 votes
3 3 answers
2.9k
2.9k views
Is the following language CFL?
Not able to understand whether it is CFL or not due to the condition 'm>=481'.
User Avatar
1 1 vote
2 answers 2 answers
1.6k
1.6k views
DCFL or not??
$L1 = \bigl\{a^mb^nc^pd^q \mid m+q = n+p \bigr\}$$L2 = \bigl\{a^mb^nc^pd^q \mid m+p = n+q \bigr\}$1. L1 is DCFL, L2 is not2. L2 is DCFL, L1 is not3. Both are not DCFL...
User Avatar
Page: