in Theory of Computation retagged by
5,013 views
18 votes
18 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.
in Theory of Computation retagged by
5.0k views

2 Answers

22 votes
22 votes
Best answer

$L=\{a^n c b^{2n}\}$
$\quad=\{acbb,aacbbbb,aaacbbbbbb,\ldots\}$

Here, $\textbf{c}$ acts as center. Push $2$ $a$'s for each $\textbf{a}$  and after $\textbf{c}$ start popping an $\textbf{a}$ for each $\textbf{b}$. If stack is empty and string is finished we move to $q_2$ which is the acceptance state.

edited by

4 Comments

Sir,  I am confuse the main difference between empty stack and final state in PDA
0
0

https://youtu.be/SZoRVBgwDwk

In this video, he said that putting two 'a's' on reading one 'a' is not valid. Can someone please clarify I am confused. @Arjun @Saraswati Walujkar

0
0
DPDA in this answer is accepting “c" means n=0

If I am wrong, then please tell me how it's ensuring n!=0
0
0
2 votes
2 votes

Two way to draw it

2 figure) For single  input a push two a's on stack for state 0 and when c comes then don't do anything and change the state to 1 now as b will come the then top of the stack will have a then pop the a's for b's ,so when stack becomes empty then on seeing the input Null we can accept it by changing state to 2 (final) state.

1 figure) by pushing a's then don't do anything as c comes and move to state to 1 now if b comes then top of stack has a, don't do anything for first b (move to state 2)then for second b pop  the a(move to state 3) repeat steps if there are more a's on the stack (as shown in figure,by moving from state 3 to state 2 ) otherwise accept it by moving from state 3 to 4.

Related questions