<p>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\}$.</p>

CC BY-SA 3.0
2014-07-06T08:13:33.213Z
2014-07-06T08:13:33.213Z
sdcvvc
<p>A proof that uses closure properties:</p>

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

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

<p>$L'_1 = \{ \alpha \# w \mid w \in L_1\}$<br>
$L'_2 = \{ \beta \# w \mid w \in L_1\}$</p>

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

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

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

<p>too.</p>

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

CC BY-SA 3.0
2014-07-06T13:22:10.677Z
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
CC BY-SA 3.0
2014-07-06T16:48:14.993Z
@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
CC BY-SA 3.0
2014-07-06T20:56:31.203Z
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
CC BY-SA 3.0
2014-07-06T21:40:25.397Z
@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
CC BY-SA 3.0
2014-07-06T10:38:29.913Z
2014-07-06T10:38:29.913Z
Marzio De Biasi
<p>Define the outfix of a language $L$ to be
$Outf(L) = \{xy \mid \exists z. xzy \in L \}$.</p>

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

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

CC BY-SA 3.0
2014-07-05T18:50:30.383Z
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
CC BY-SA 3.0
2014-07-05T19:37:06.100Z
No worries! Yeah, these erasing operations are always the trickier with the deterministic version.
Joey Eremondi
<reference-request><fl.formal-languages><automata-theory><context-free>
Are deterministic context-free languages closed under outfix (or other erasing operations)
Joey Eremondi
# Are deterministic context-free languages closed under outfix (or other erasing operations)

(Asked by: username_0 on 2014-07-04)

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.

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

> **Comments:**
> **username_1**: I removed my answer ... I had this feeling I maust have missed a word ... butI could not see it, even after rereading the question.  
> **username_0**: No worries! Yeah, these erasing operations are always the trickier with the deterministic version.  

---

## 2 answers

### Answer by username_3 on 2014-07-06. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_1**: This proof is essentially similar to the  counter-example given previously by username_2, though he skipped explaining. He uses b instead of # as a guard against erasing.  
> **username_3**: @username_1: yes the idea is the same! But I read (carefully) his example only after posting my answer :(. The OP should accept username_2's answer instead of mine, if both are what he needed.  
> **username_1**: 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.  
> **username_3**: @username_1: I agree with you, my comment was only a suggestion for the OP to accept username_2's answer which is a nice succinct representation of the same idea (and was posted first :-)  

---

### Answer by username_2 on 2014-07-06. Score: 3

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\}$.


---

