0 votes 0 votes DPDA for $L = \left \{ a^nb^m|m\geq n+2 \right \}$ Theory of Computation theory-of-computation pushdown-automata + – dd asked Dec 7, 2016 dd 487 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply mohit chawla commented Dec 7, 2016 reply Follow Share 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. 0 votes 0 votes dd commented Dec 7, 2016 reply Follow Share http://madebyevan.com/fsm/ just two mins :) 2 votes 2 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes State 1 : Count a State 2 : Count b State 3 : Count 1st b State 4 : Count 2nd b and accept State 5 : Reject Kapil answered Dec 7, 2016 • selected Dec 7, 2016 by pC Kapil comment Share Follow See 1 comment See all 1 1 comment reply PEKKA commented Dec 7, 2016 reply Follow Share @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 . 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes push all a's, pop an 'a' for every b,see that u have atleast 2 b's after stack is empty Anusha Motamarri answered Dec 7, 2016 Anusha Motamarri comment Share Follow See all 0 reply Please log in or register to add a comment.