search
Log In
1 vote
326 views
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.
in Theory of Computation 326 views

2 Answers

2 votes

Acceptance by empty stack.

 

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

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

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

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

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

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

Related questions

0 votes
0 answers
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,λ)$}.
asked Jun 23, 2019 in Theory of Computation Naveen Kumar 3 69 views
0 votes
0 answers
3
68 views
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)$}.
asked Jun 23, 2019 in Theory of Computation Naveen Kumar 3 68 views
...