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 10 (Page No. 195)

1 vote
118 views
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.
in Theory of Computation 118 views

1 Answer

2 votes

for every 'a' push two a's and see b's match it off and acceptance by empty stack

 

← 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
...