6
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – babou Jul 6 '14 at 13:22
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Jul 6 '14 at 16:48
  • $\begingroup$ 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. $\endgroup$ – babou Jul 6 '14 at 20:56
  • $\begingroup$ @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 :-) $\endgroup$ – Marzio De Biasi Jul 6 '14 at 21:40
3
$\begingroup$

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

$\endgroup$

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.