The Gateway to Computer Science Excellence
+15 votes
706 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.
in Theory of Computation by Veteran (52.2k points)
retagged by | 706 views

2 Answers

+19 votes
Best answer

$L=\{a^n c b^{2n}\}$
$\qquad=\{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.

by (403 points)
edited by
+2
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).
0
@pooja khatri
  above diagram is  follow empty stack right??

  what about Final state diagram?
0
How is it following empty stack property? It has a Final state.
0
Sir,  I am confuse the main difference between empty stack and final state in PDA
0

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

+1 vote

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.

by Loyal (5.7k points)

Related questions

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
50,647 questions
56,465 answers
195,380 comments
100,303 users