344 views
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.
retagged | 344 views

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

={acbb,aacbbbb,aaacbbbbbb,.......}

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

selected
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).