# 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.

## migrated from cstheory.stackexchange.comOct 7 '12 at 16:31

This question came from our site for theoretical computer scientists and researchers in related fields.

• 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. – Janoma Jan 15 '12 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. – Sam Jones Jan 15 '12 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. – Janoma Jan 16 '12 at 0:56
• DCFL are defined by acceptance by final state. – Emil Jeřábek Jan 16 '12 at 11:49
• One related question, another related question (for regular languages) and yet another related question. – Ran G. Oct 7 '12 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. – Raphael Jan 18 '13 at 15:17