menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

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$}.
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,λ)

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

0 votes
0 answers
1
69 views
Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
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 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
Peter Linz Edition 4 Exercise 7.2 Question 11,12,13 (Page No. 195)
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 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
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
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...