# Closure of Deterministic context-free languages under prefix

For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:

$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$

ie. the set of all (not necessarily proper) prefixes of words in $L$. I know that if $L$ is context-free then pref(L) is context-free but if $L$ is deterministic context-free then is pref(L) deterministic context-free?

I am sure this is known but I cannot find the answer anywhere and it's not in Hopcroft and Ullman.

• Have you tried finding a counterexample or a proof? Also, can you specify your model of pushdown automaton? I mean, do you use a special symbol $Z_0$ at the bottom of the stack? What is the condition for acceptance of a word (empty stack, final state, both at the same time)? You need to clarify that to properly justify your proof or counterexample. Still, it looks like homework problem, I'm not sure this is the right place to post your question. Jan 15, 2012 at 22:35
• I can see how to do it non-deterministically, but to do it deterministically is not obvious to me. I feel that there might be a counterexample but again I have not been able to find one. The Deterministic Context-free languages are well defined and so any model which accepts precisely the Deterministic Context-Free languages (In the Hopcroft and Ullman sense, if there really are multiple models referred to as DCFL) is fine. I have seen this question for CFL set as homework but not for DCFL, if it were one would expect it to be easy to find the answer. Jan 15, 2012 at 23:48
• Unlike with nondeterministic pushdown automata, acceptance by final state and acceptance by empty stack are not equivalent for DPDA, that's why I wanted that clarified. I don't have the book (Hopcroft&Ullman) with me, so I can't check the definition. Jan 16, 2012 at 0:56
• DCFL are defined by acceptance by final state.
– Emil Jeřábek
Jan 16, 2012 at 11:49
• One related question, another related question (for regular languages) and yet another related question. Oct 7, 2012 at 17:32

DCFL are known to be closed under quotient with regular languages, but the quotient of $L$ with $\Sigma^{*}$ is precisely $\text{pref}(L)$ so yes, if $L$ is a DCFL then $\text{pref}(L)$ is a DCFL.
• Can you add a reference for the claim that $\mathrm{DCFL} \subseteq \operatorname{LR}(0)$? The part in parentheses seem to be more of a comment, rather than an answer. Jan 18, 2013 at 15:17