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
