[Solved]: Are DCFLs closed under reversal?

Problem Detail: 

According to this chart, DCFLs are closed under reversal.

However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and pops) for this seems to depend on non-determinism in choosing the null transition to take from the initial state (since the new initial state would contain a null transition to all the old final states).

This would make the "reverse PDA" of a DPDA non-deterministic whenever there is more than a single final state in the original DPDA.

What is the fallacy in my argument? Or is there another way to go about proving this?

Asked By : peteykun

Answered By : babou

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter.

Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted):

$(a+b+c)^*WcW^R$, where $W \in (a+b)^+$; this is non-deterministic because you don't know where the $WcW$ bit starts.

$W^RcW(a+b+c)^*$, where $W \in (a+b)^+$; this is deterministic because you can write a deterministic PDA to accept simple palindromes of the form $W^RcW$ and modify the accepting state to loop to itself on any of $a$, $b$ and $c$.

The trick here is that PDAs have to read input from left to right.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30702