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?

$\endgroup$
  • 3
    $\begingroup$ For what's worth, this result holds for any $LR$ where $R$ is regular (see here). $\endgroup$ – sdcvvc Jul 10 '13 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 '13 at 5:11
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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