[Solved]: Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

Problem Detail: 

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?

Asked By : jmite

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13179

 Ask a Question

 Download Related Notes/Documents