patternModerate
Are DCFLs closed under reversal?
Viewed 0 times
dcflsareclosedunderreversal
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#30702, answer score: 10
Revisions (0)
No revisions yet.