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

-

DCFLs have LR(0) grammars, and LR parsers have the property that they report the error on the first symbol that can't be legally there. So the strategy would be simply to run the LR parser and accept whatever doesn't give an error before ending the string. (Way overkill, there must be a "simpler" way to prove it, but this convinces me that the result is in fact true. Building a DPDA for the prefixes isn't so easy, a DPDA could just fall into some kind of loop eating up the string without any chance of accepting at the end; to prove it directly by that route you'd have to make sure somehow that if there are legal moves from the current state, there is a path that leads to ultimate acceptance with some remainder, and that looks messy.)

-
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

According the concept of context free language very context can be represented in the form of "CHOMSKY NORMAL FORM".so if in the rule we made change like if A->BC change it to the A->BC/B now this type of replacement will generate the context free language of prefix language of the given

-
sorry... What?! –  Ran G. Oct 7 '12 at 17:38
(I think) I know what you're trying to say, but unfortunately it doesn't work and a correct answer has already been posted above. –  Sam Jones Oct 10 '12 at 11:14