DCFL or CFL

Question

{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 !!

Comments

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

---

Oh yes !! I studied this how can I forget :/ My bad ! Anyways thank you :)

Answer 1

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.

Answer 2

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.)