# Recent questions tagged npda

0 votes
2 answers
1
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
0 votes
6 answers
2
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.
0 votes
0 answers
3
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).
0 votes
0 answers
4
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.
0 votes
0 answers
5
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,λ)$}.
0 votes
0 answers
6
find an npda for the language $L =${ $ww^R : w ∈$ {a, b}$^+$}
0 votes
0 answers
7
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 : Consider the npda with transitions $\delta(q_0,a,z)=$ ... $(q_0,A)$}, $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
1 vote
1 answer
8
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.
1 vote
2 answers
9
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.
0 votes
0 answers
10
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$. Show how the number of states of $\widehat M$ in the above exercise can be reduced to two.
0 votes
0 answers
11
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$
0 votes
1 answer
12
Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.
0 votes
0 answers
13
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.
0 votes
0 answers
14
We can define a restricted npda as one that can increase the length of the stack by at most one symbol in each move, changing Definition 7.1 so that $\delta :$Q x $(\sum \cup$ {$\lambda$}$)$ $\Gamma \rightarrow 2^{Q (\Gamma \Gamma \cup \Gamma \cup {\lambda})}$ The ... , $q_0 ∈ Q$ is the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.
0 votes
0 answers
15
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.
0 votes
0 answers
16
What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?
0 votes
0 answers
17
What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) with transitions $\delta(q_0,a,z)=${$(q_1,a),(q_2,\lambda)$}, $\delta(q_1,b,a)=${$(q_1,b)$}, $\delta(q_1,b,b)=${$(q_1,b)$}, $\delta(q_1,a,b)=${$(q_2,\lambda)$} ?
0 votes
0 answers
18
What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}), with $\delta(q_0,b,z)=${$(q_1,1z)$}, $\delta(q_0,b,1)=${$(q_1,11)$}, $\delta(q_2,a,1)=${$(q_3,\lambda)$}, $\delta(q_3,a,1)=${$(q_4,\lambda)$} $\delta(q_4,a,z)=${$(q_4,z),(q_5,z)$} ?
0 votes
0 answers
19
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?
0 votes
0 answers
20
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.
0 votes
0 answers
21
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.
0 votes
0 answers
22
Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.
0 votes
0 answers
23
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.
0 votes
0 answers
24
Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}. (a) $L =$ {$a^nb^{2n} : n ≥ 0$}. (b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}. (c) $L =$ {$a^nb^mc^{n+m} : n ≥ 0, m ≥ 0$}. (d) $L =$ {$a^nb^{n+m}c^m : n ≥ 0, m ≥ 1$}. (e) $L =$ {$a^3b^nc^n : n ≥ 0$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.
1 vote
0 answers
25
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)
0 votes
0 answers
26
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.
0 votes
1 answer
27
WHAT WILL BE THE ANS?
0 votes
0 answers
28
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
1 vote
2 answers
29
Q. {al bm cn | l ≠ m or m ≠ n} construct a PDA for this language?
0 votes
1 answer
30
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?