# Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$.

Are any known results about whether deterministic context-free languages are closed under this operation, or other similar "erasing" operations?

My preliminary search has not turned up anything, but I thought someone who had knowledge of the area might know of a reference.

• I removed my answer ... I had this feeling I maust have missed a word ... butI could not see it, even after rereading the question. – babou Jul 5 '14 at 18:50
• No worries! Yeah, these erasing operations are always the trickier with the deterministic version. – jmite Jul 5 '14 at 19:37

A proof that uses closure properties:

DCF languages are not closed under union, so take, $L_1, L_2 \in DCF$ s.t. $L = L_1 \cup L_2 \notin DCF$

Add three new symbols $\{\alpha, \beta, \#\}$ to the original alphabet $\Sigma$ and build the languages:

$L'_1 = \{ \alpha \# w \mid w \in L_1\}$
$L'_2 = \{ \beta \# w \mid w \in L_1\}$

We have $L'_1, L'_2$, but also $L' = L'_1 \cup L'_2 \in DCF$ (it is enough to add a starting state that leads to the recognition of $\#L_1$ after reading a leading symbol $\alpha$ or the recognition of $\#L_2$ after reading a leading symbol $\beta$).

Now suppose that $Outf(L') \in DCF$; we know that DCFs are closed under intersection with regular languages, so:

$$Outf(L') \cap \{ \#w \mid w\in \Sigma^*\} = \{ \#w \mid w\in L_1 \lor w \in L_2 \} \in DCF$$

too.

But given a DPDA for $Outf(L') \cap \{ \#w \mid w\in \Sigma^*\}$ it is immediate to build a DPDA for $\{ w \mid w \in L_1 \lor w \in L_2\} = L$ (just skip the recognition of the first leading symbol $\#$), so $L \in DCF$ contradicting the hypothesis.

• This proof is essentially similar to the counter-example given previously by sdcvvc, though he skipped explaining. He uses b instead of # as a guard against erasing. – babou Jul 6 '14 at 13:22
• @babou: yes the idea is the same! But I read (carefully) his example only after posting my answer :(. The OP should accept sdcvvc's answer instead of mine, if both are what he needed. – Marzio De Biasi Jul 6 '14 at 16:48
• I did not imply that you were inspired by him. I was just reacting to the fact that he was getting no vote, which I thought unfair. It is true that he could have explained in more details ... but since everyone keeps repeating that this is a research site, one could expect the readers to be big boys enough to understand without explanation, or to ask for more details. BTW I like the way you avoid having to choose specific DCF languages. – babou Jul 6 '14 at 20:56
• @babou: I agree with you, my comment was only a suggestion for the OP to accept sdcvvc's answer which is a nice succinct representation of the same idea (and was posted first :-) – Marzio De Biasi Jul 6 '14 at 21:40

Consider $Outf(\{a^n b x b c^n\} \cup \{a^n b y b c^{2n}\}) \cap a^{\ast} b b c^{\ast}$ over alphabet $\{a,b,c,x,y\}$.