# Peter Linz Edition 4 Exercise 7.2 Question 9 (Page No. 195)

1 vote
326 views
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.

Acceptance by empty stack.

0
is the transition (b,z0,zo) required??

𝛿( q0 , λ , z)  →  ( q0 , Sz1 )

𝛿( q0,a,S)→  { ( q0 , SB ) }

𝛿( q0,b,S)→ (q0,λ)

𝛿( q0,b,B)→ (q0,λ)

𝛿( q0,λ,z1)→ (q0,λ)

## Related questions

1
69 views
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,λ)$}.
find an npda for the language $L =${ $ww^R : w ∈$ {a, b}$^+$}
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)$}.
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.