5
$\begingroup$

So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ and each final state $q$, you add a transition looping from $q$ to $q$ on $a$.

I'm using this in a paper, and I'd love to not have to actually prove this construction is valid. It's easy, but it's about a half-page long. Since DPDAs have been studied almost exhaustively, I was wondering, does anybody know of a paper that proves this property?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ For what's worth, this result holds for any $LR$ where $R$ is regular (see here). $\endgroup$
    – sdcvvc
    Jul 10, 2013 at 1:38
  • $\begingroup$ That's awesome. You wouldn't know of a paper with that in it that I could cite, do you? $\endgroup$
    – jmite
    Jul 10, 2013 at 5:11

1 Answer 1

Reset to default
4
$\begingroup$

One of the early works on DCFL is Seymour Ginsburg, Sheila Greibach: Deterministic context free languages, Information and Control, Volume 9, Issue 6, December 1966, Pages 620–648, doi:10.1016/S0019-9958(66)80019-0

The paper has various closure properties, for instance closure under complement (mind that my old Hopcroft and Ullman book states ".. was observed independently by various people") and closure under quotient with regular languages.

Closure of DCFL under concatenation with regular languages is the result you need, which is Theorem 3.3 from the paper.

Improve this answer
$\endgroup$

Your Answer

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

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