DCFL or CFL ?

Question

Isn't WxWr DCFL as X acts as marker so DCFL should be right choice , why is it categorized as CFL and not DCFL?

Answer 1

wxw^r 

see take w as 001

x as 101

w^r  will be 100

001 101 100

above string will be accepted in non deterministically way only ,at each step we have  two copies  (i e one for push and other for pop ) to match 001 with reverse of it .therefore 

so it is cfl  but not dcfl .

Comments

This is because x belongs to {0,1} right , what if question didn't have any such specification ? Would it be deterministic then ? In which case , it would be deterministic or we can consider X as marker which DPDA can undestand ?

---

First of all x which you have taken 101 is wrong.
x can be only 0 or 1.

here center symbol is not sure because x contains the alphabet of w ie.{0,1}. so at each step there is a non determination that whether to push or pop. So it is CFL not DCFL.

for eg. 110 0 011 : center 0 will be push or pop is not clear.

110 1 011 : center 1 is not clear whether to push or pop. here center may be part of w or it may be of x so non determination is coming.

Answer 2

Both of them will DCFL and none of them will CFL.

For first language there exist DPDA,

Bcz whenever we encounter 'a' we simply push on the stack,when all 'a' are over then we start pushing 'b' when all 'b' are finish and after getting first 'c' and subsequent 'c' we pop all 'b' from the top of the stack.When all 'c' and all 'b' are over and only stack contains 'a' and input remaining 'd' ,then we pop each 'a' against all 'b'..Therefore, first languages is accepted by DCFl.

L={wxw^r/w belong to (a,b)+}

It is nothing but string starting with same symbol.For varification put some binary data and check

Therefore it must be DCFL.