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$
2
  • 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
    Commented Jul 5, 2014 at 18:50
  • $\begingroup$ No worries! Yeah, these erasing operations are always the trickier with the deterministic version. $\endgroup$ Commented Jul 5, 2014 at 19:37

2 Answers 2

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$
4
  • $\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
    Commented Jul 6, 2014 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$ Commented Jul 6, 2014 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
    Commented Jul 6, 2014 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$ Commented Jul 6, 2014 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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.