The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 votes
Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.
asked in Theory of Computation by Veteran (59.4k points)
retagged by | 381 views

1 Answer

+13 votes
Best answer

$L=\{a^n c b^2n\}$


Here '$c$' act as center. Push $2$ $a$'s for $1$ '$a$'  and when you see '$c$' pop the $b$'s


answered by (419 points)
edited by
you can't set q1 as an accepting state because if suppose string is aacb then it will be accepted. So, you have to make one more state from q1 to  q2( i.e final state) for the (e, Zo / Zo).

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

34,770 questions
41,731 answers
41,381 users