<p>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&#39;=\{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!}$). </p>

CC BY-SA 2.5
2011-03-23T12:33:00.580Z
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?
Martin Berger
CC BY-SA 2.5
2011-03-23T16:10:36.437Z
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.
Sylvain
CC BY-SA 2.5
2011-03-23T20:05:58.687Z
Yes, something like that. Since this does not work, I will have to re-design my application domain. Thanks very much for your input.
Martin Berger
CC BY-SA 2.5
2011-03-22T08:49:15.083Z
2011-03-22T08:49:15.083Z
Sylvain
<p>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)$?</p>

<p>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.</p>

<fl.formal-languages><automata-theory><grammars><context-free-languages>
Closure of unambiguous context-free languages under pre- and postfix.
Martin Berger
# Closure of unambiguous context-free languages under pre- and postfix.

(Asked by: username_0 on 2011-03-22)

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.

**Tags:** fl.formal-languages, automata-theory, grammars, context-free-languages


---

## 1 answers

### Answer by username_1 on 2011-03-22. Score: 12 | Accepted answer

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!}$).

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: Yes, something like that. Since this does not work, I will have to re-design my application domain. Thanks very much for your input.  

---

