dpda || Linz 7.3-2

Question

DPDA for $L = \left \{ a^nb^m|m\geq n+2 \right \}$

Comments

it's easy,i am giving you hint, be at initial state q0 and push as many a's as you see, when you encounter 1st b, go to state q1 and start poping a's for every b. now after a while you will reach a stage where you have b's on the i/p tape but no. of a's is 0 in stack due to poping. now read next 'b' and go to a different state q2 and go to another state q3 after reading  next b and don't do anything to stack during this. now condition is satisfied. now for every 'b' , don't do anything on stack, just read it. atlast when i/p string is empty and stack conatins "Z0(stack symbol)" go to final state.

---

http://madebyevan.com/fsm/ just two mins :)

Answer 1

State 1 : Count a

State 2 : Count b

State 3 : Count 1st b

State 4 : Count 2nd b and accept

State 5 : Reject
 

Comments

@Kapil Sir  , I have got some doubt in your transitions  can u correct / add poits where im lacking

State 1

(a,z/az) -> input is a  stack top is z then 'push a ' to stack   stack become az

(a,a/aa) -> input a  stack top is z then push a to stack  . stack become aa

State 2

(b,a/^) -> on input b pop stack top untill all elements are poped out  

state 3

(b,z/bz)-> on input b and initial stack element z  push b to stack

state 4

(b,b/bb) - > ON input b stack top b push b to stack . 
 

Answer 2

push all a's, pop an 'a' for every b,see that u have atleast 2 b's after stack is empty