Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
For what's worth, this result holds for any $LR$ where $R$ is regular (see here). – sdcvvc Jul 10 '13 at 1:38
That's awesome. You wouldn't know of a paper with that in it that I could cite, do you? – jmite Jul 10 '13 at 5:11
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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