The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
51 views

Can we put simultanously Two symbols in stack in one of the video on youtube it is showing that we can put two a's on to the stack I'm not finding it correct plzz calrify my doubt it on place of one a we are putting two a's one extra a is also there  what about that because any how 1 b is poping out 1 a then no.of b's will be fine but what about one extra which has been take out

asked in Theory of Computation by (275 points) | 51 views
+1

you just did a little mistake 

an we put simultanously Two symbols in stack

so on reading one a push 2X where x is a new symbol so we can always check the number of a=2b ( you can put any new symbol )

eg aabbbb

The 1st a  stack is XX

on 2nd a stack is XXXX

now on one b pop one X

1st b stack is XXX

2nd b stack is XX

3rd b stack is X

and 4th b stack is {}

if the stack is not empty then  a$\neq$2b

1 Answer

+2 votes
Best answer
$L=a^{n}b^{2n} | n>=1$

So, The PDA that you drew. Let me explain how it will roll when you give it an input like "aabbbb" i.e. $a^2b^4$ which is in above language.
State-1 : a,z0--->aaz0  {whenever you see input 'a' and top of the stack is 'z0' or I/P is 'a' and top of the stack is 'a', push 'a' and again 'a' i.e.two times 'aa' and yes we can do that, make our PDA like that you can insert 'aa', 'aaa', 'aaaa' any number of 'a's. To understand this you must know how Finite Automata machines can on certain input produce an output, these machines also known as FINITE STATE TRANSDUCER.}

Now every time PDA read input 'a' it will push 'aa' (two a's ) in the stack. WHY? because no. of b's are two times the number of a's.
so when you finish reading two a's from the input stack will have 4 a's in it and when we encounter b's in state-1 we move state-2 poping each 'a' for every 'b'. So now on stack there 4 a's and on the input string, there are 4 b's. You now know how things gonna pop out. Hence input string 'aabbbb' will be accepted by the PDA that you draw above.
answered by Active (3.9k points)
selected by


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

40,903 questions
47,560 answers
146,294 comments
62,306 users