10
$\begingroup$

Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: if $L$ is context-free and has a non-ambiguous grammar, is the same true for $ppc(L)$?

I believe that this kind of basic question would already have been resolved in the heyday of language theory, but I could not find a suitable reference.

$\endgroup$
12
$\begingroup$

The set $\mathit{ppc}(L)$ is certainly context-free, but I think it can be inherently ambiguous: consider $$L=\{a^mb^mc^nd\mid m,n\geq 0\}\cup\{da^mb^nc^n\mid m,n\geq 0\}\;,$$ then $\mathit{ppc}(L)$ includes the classical inherently ambiguous language $$L'=\{a^mb^mc^n\mid m,n\geq 0\}\cup\{a^mb^nc^n\mid m,n\geq 0\}\;,$$ and one can prove $\mathit{ppc}(L)$ is also inherently ambiguous by the usual argument (apply Ogden's Lemma to both $a^{n+n!}b^nc^n$ and $a^nb^nc^{n+n!}$ to deduce the existence of two distinct trees for $a^{n+n!}b^{n+n!}c^{n+n!}$).

$\endgroup$
  • $\begingroup$ Thank you. That was easier than I though. Do you think variants of the problem (e.g. the pre- and postfixes must be delimited (by new symbols) exhibit a similar loss of non-ambiguity? $\endgroup$ – Martin Berger Mar 23 '11 at 12:33
  • $\begingroup$ Do you mean something like $\mathit{ppc}_\$(L)=\{w\$\mid\exists w',\,ww'\in L\}\cup\{\$w\mid\exists w',\,w'w\in L\}$? Then starting from $L=\{da^mb^mc^n\mid m,n\geq 0\}\cup\{ea^mb^nc^n\mid m,n\geq 0\}$ you would find that $\$a^{n+n!}b^{n+n!}c^{n+n!}$ has two distinct trees in any grammar for $\mathit{ppc}_\$(L)$. I am afraid I do not have any idea at the moment about how one could modify (in a simple way) the $\mathit{ppc}$ operation in order to ensure unambiguity: the prefix or suffix lost in the operation might be crucial for unambiguity to hold. $\endgroup$ – Sylvain Mar 23 '11 at 16:10
  • 1
    $\begingroup$ Yes, something like that. Since this does not work, I will have to re-design my application domain. Thanks very much for your input. $\endgroup$ – Martin Berger Mar 23 '11 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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