2 votes 2 votes {w| number of Zeros=number of Ones} Alphabet= {0,1} It is a CFL for sure. But,is it also a DCFL i.e. can we construct a DPDA for it? My Approach:: for 0 push in stack , for 1's pop ---> In end stack should be empty Hence, a DCFL. But, eg given string :: 1100 Now,for 1's pop but, nothing in stack to pop .... STUCK HERE !! Theory of Computation theory-of-computation dcfl + – VS asked Aug 8, 2017 VS 492 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply joshi_nitish commented Aug 8, 2017 reply Follow Share it is DCFL.. if same alphabet or 'z'(stack start symbol), is seen on top of stack, then push, else if different alphabet is seen pop...atlast if emty stack, than accept 1 votes 1 votes VS commented Aug 8, 2017 reply Follow Share Oh yes !! I studied this how can I forget :/ My bad ! Anyways thank you :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It is DCFL, we need to look at first alphabet here and identify our actions 1) If first albhabet is 0, we push every 0 on to the stack, and for every 1 we pop one 0. 2) Similarly if first alphabet is 1, we push every 1 on to the stack, and for every 0 we pop one 1. 3) If we end up with empty stack accept else reject. stblue answered Aug 8, 2017 stblue comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes You can follow 6 condition If (0 input and stack is null then push 0) else if (0 input and stack has 1 then pop 1.) else if (0 input and stack has 0 then push 0.) else if (1 input and stack is null then push 1) else if (1 input and stack has 0 then pop 0.) else if (0 input and stack has 1 then push 1.) Brij Mohan Gupta answered Aug 8, 2017 Brij Mohan Gupta comment Share Follow See all 0 reply Please log in or register to add a comment.