+1 vote
62 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

+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

$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.
selected by