search
Log In

Recent questions tagged dpda

0 votes
6 answers
1
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 344 views
0 votes
0 answers
2
The proof of Lemma $2.41$ says that $(q, x)$ is a looping situation for a $DPDA \:P$ if when $P$ is started in state $q$ with $x \in \Gamma$ on the top of the stack, it never pops anything below $x$ and it never reads an input symbol. Show that $F$ is decidable, where $F = \{ \langle P, q, x \rangle \mid (q, x)\: \text{is a looping situation for P}\}$.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 65 views
0 votes
0 answers
3
The purpose of this exercise is to show that a one-stack machine with an endmarker on the input has no more power than a deterministic $PDA$. $L\$ is the concatenation of language $L$ with the language containing only the one string $\$; that is, $L\$ is the set of all strings $w\$ such ... is the set of states $q$ such that $P$,started in $ID\ (q,a,X_{i}X_{i+1}\cdot \cdot X_{n})$ will accept.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
4
0 votes
1 answer
5
What should be the approach to draw the DFA - "All strings that have exactly one double letter in them" on symbols {a,b}.
asked Nov 12, 2018 in Theory of Computation Jeevesh 132 views
0 votes
1 answer
6
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack Then A)Ldf proper subset of Lef. B)Ldf = Lef. C)Lef proper subset of Ldf. D)None .
asked Nov 6, 2018 in Theory of Computation Abhisek Tiwari 4 179 views
0 votes
2 answers
7
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
asked Oct 25, 2018 in Theory of Computation Shamim Ahmed 184 views
0 votes
0 answers
9
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.
asked Jul 28, 2018 in Theory of Computation Matrix 560 views
1 vote
1 answer
10
Consider the following statements about the context free grammar G = {S-->SS , S-->ab , S-->ba , S-->^} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about ? A) I only B) I and III C) II and II D) All I,II,III In a answer key shown answer D but II is not right.
asked Jun 13, 2018 in Theory of Computation Nikhil Patil 284 views
0 votes
1 answer
12
4 votes
0 answers
13
Construct a PDA for the language of all those strings in which the number of $b 's$ is double the number of $a 's$. $a$ and $b$ can occur in any order. For example: $L=\{\text{^}, abb, bab, bba, aabbbb, ababbb, abbbabb, abbbab, abbba, ...... \}$
asked Mar 28, 2018 in Theory of Computation The Capricorn 206 views
2 votes
1 answer
14
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 ?
asked Mar 4, 2018 in Theory of Computation ankitgupta.1729 148 views
0 votes
1 answer
15
How can we show that { anbm, m>= n+2} is deterministic ? for eg for a4b6 or in general ?
asked Dec 11, 2017 in Theory of Computation Pawan Kumar 2 62 views
1 vote
2 answers
16
0 votes
0 answers
17
Consider the following statement: S: Set of languages accepted by DPDA by empty stack contain only those DCFL’s with prefix property. Please explain as why this sentence is wrong....
asked Dec 1, 2017 in Theory of Computation shivangi5 111 views
8 votes
1 answer
18
How to find DPDA’s that accept by null stack? Someone explain the prefix property for DPDA,How can we use this property?
asked Nov 2, 2017 in Theory of Computation set2018 1.2k views
3 votes
0 answers
19
1) Can a Deterministic PDA has two epsilon transition each reading different Stack symbol to perform a transition? 2) Can a transition be performed without reading Stack symbol at all. Like $ a, λ/ λ$?
asked Oct 22, 2017 in Theory of Computation AskHerOut 139 views
0 votes
0 answers
20
The following question is a modified version of this question https://gateoverflow.in/3785/gate2005-it-38, in this GATE question they have NPDA, but I'm asking about DPDA Let D be a deterministic push-down automaton (DPDA) with exactly one state, q, and exactly one symbol, Z, in its stack ... P) is not necessarily Σ*. Both L(P) and N(P) are necessarily Σ*. Neither L(P) nor N(P) are necessarily Σ*.
asked Sep 17, 2017 in Theory of Computation iarnav 221 views
0 votes
0 answers
21
1 vote
1 answer
23
What is main difference between Deterministic Push down automata and simple Push down automata ?
asked Aug 15, 2017 in Theory of Computation ashutoshaay26 524 views
To see more, click for the full list of questions or popular tags.
...