8
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Please let me know if my StackOverflow answer requires any additional explanation. The problem with your proof attempt is this: the PDA you construct isn't the only PDA for the language it accepts. There might be others, possibly arrived at differently, which are deterministic. In particular, DCFLs can be accepted by PDAs that aren't deterministic. $\endgroup$
    – Patrick87
    Commented Oct 7, 2014 at 14:09
  • $\begingroup$ Right, which is why I realize this is not much of a "proof" at all, it would only have meaning if the result was always a DCFL, which it is not. I guess I was just trying to prove it using the same method as is used for Regular languages and failed. Thanks for the counter example! $\endgroup$
    – peteykun
    Commented Oct 7, 2014 at 14:21
  • $\begingroup$ Consider $L={b^n c^n} \cap {a b^2n c^n} $ $\endgroup$
    – Pranav
    Commented Jan 15, 2017 at 11:01
  • $\begingroup$ That table also says recursive languages are closed $\lambda$-free substitution...is that correct? $\endgroup$
    – RajS
    Commented Dec 25, 2017 at 20:59

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is absurd. Patrick87 provided the examples, @Raphael did half the editing work, and I get the rep. Then, we get so little for real work ... :) $\endgroup$
    – babou
    Commented Oct 7, 2014 at 14:40
  • 3
    $\begingroup$ Think of it as a "finder's fee" :) I'm just mystified the system actually works well enough that you found that old post of mine. The system works! Hail SE! $\endgroup$
    – Patrick87
    Commented Oct 7, 2014 at 16:56
  • $\begingroup$ Did H&U overlook reversal for DCFL? They mention non-closure under union, concatenation, Kleene, morphism in Thm 10.5 see Exercise 10.4 (starred but with a solution). However, they note $\{ 0^i1^i2^j\mid i,j\} \cup \{ 0^i1^j2^j\mid i,j\}$ is not DCFL, so neither is $K = \{ 0^i1^i2^ja \mid i,j\} \cup \{ 0^i1^j2^jb\mid i,j\}$ by closure of DCFL under quotient with regular set, Thm 10.2. But the reversal of $K$ is a DCFL, the 'markers' $a$ and $b$ give away the information where to use the pushdown. [ Perhaps @babou can add this if he likes; he is the one collecting the reps here :) ] $\endgroup$
    – Hendrik Jan
    Commented Oct 7, 2014 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.