# Closure of unambiguous context-free languages under pre- and postfix.

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.

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!}$).
• 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. Mar 23, 2011 at 16:10