Is this language DCFL

Question

Hi , my question is : is this language D ( w x w^R ) DCFL or Non deterministic CFL ?

Answer 1

A is non linear power of a so csl

B is regular (aaa)*aaaaa

C is DCFL .

D is CFL because x belongs to 0 and 1.so we don't know exactly where is actually x, so we need to explicitly guess the 0 or 1 so that we can say after that w^R starts.

(if x is not of 0 or 1, say 2 then we know exact after that we have w^R ,then it will be DCFL)

Comments

u should say " choice is there but that choice is deterministic either with 0 or 1 can we can decide deterministically and match the upcoming string with those string which is present in stack.." so DCFL

---

Had x belonged to {0,1}* then it will be DCFL na ?

---

And now since we have only one choice for x so then how will we compare whether w^r matches w ?

---

Yes you are right, if there we had $x\in \{0,1\}^*$  , then language will become regular.

Nothing to match. and will be DCFL too.

Answer 2

  language D ( w x wR ) is DCFL
after x pop all wR with all w whichis  present in stack  so dcfl 

Comments

w x wR
 

Here, since we don't know what x is, it could be 0 or 1. So, we need a Non-Deterministic way to approach it. So, it is CFL not DCFL.