6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Jan 15, 2012 at 22:35
  • $\begingroup$ 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. $\endgroup$
    – Sam Jones
    Commented Jan 15, 2012 at 23:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Jan 16, 2012 at 0:56
  • 3
    $\begingroup$ DCFL are defined by acceptance by final state. $\endgroup$
    – Emil Jeřábek
    Commented Jan 16, 2012 at 11:49
  • 1
    $\begingroup$ One related question, another related question (for regular languages) and yet another related question. $\endgroup$
    – Ran G.
    Commented Oct 7, 2012 at 17:32

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jan 18, 2013 at 15:17
-1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ sorry... What?! $\endgroup$
    – Ran G.
    Commented Oct 7, 2012 at 17:38
  • $\begingroup$ (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. $\endgroup$
    – Sam Jones
    Commented Oct 10, 2012 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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