# Recent questions tagged dpda 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.
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}\}$.
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.
4
L = { a^m b^n c^k=m+n } Please draw PDA for this Language!
5
What should be the approach to draw the DFA - "All strings that have exactly one double letter in them" on symbols {a,b}.
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 .
7
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
8
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.
1 vote
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.
11
12
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?
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, ...... \}$
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 ?
15
How can we show that { anbm, m>= n+2} is deterministic ? for eg for a4b6 or in general ?
1 vote
16
Realtime DPDA with Null Store,Real time DPDA with final state, DPDA with NULL store,DPDA with final state, NPDA
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....
18
How to find DPDA’s that accept by null stack? Someone explain the prefix property for DPDA,How can we use this property?
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, λ/ λ$?
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 Σ*.