498 views
1 votes
1 votes

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 Answer

Best answer
2 votes
2 votes
$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

Related questions

0 votes
0 votes
2 answers
3
Alakhator asked Nov 11, 2018
898 views
Construct a PDA for set of strings over {a,b,c,d} such thatL={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}
0 votes
0 votes
1 answer
4
Abhisek Tiwari 4 asked Nov 6, 2018
717 views
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack ThenA)Ldf proper subset of Lef.B)Ldf = Lef.C)Lef ...