7
$\begingroup$

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. Given this, if $L$ is context-free, must $FH(L)$ be context-free?

Here's my attempt at a proof:

Since $L$ is a CFL, there exists a non-deterministic PDA recognizing $L$, $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, where $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, and $Z_0$ is the symbol representing the initial stack contents. Construct PDA $M'$ from $M$, with $M' = (Q', \Sigma, \Gamma, \delta', q_0', Z_0, F')$, defined as follows:

$Q' = {q_0'} \cup (Q \times \Gamma_{\varepsilon}) \times (Q \times \Gamma_{\varepsilon}) \times (Q \times \Gamma_{\varepsilon})$.

$F' = \{[(q,X),(q,X),(p,Y)] : X,Y \in \Gamma_\varepsilon \text{ and } p \in F\}$

$\delta'(q'_0, \varepsilon, \varepsilon) = \{([(q,X), (q_0,Y), (q,X)], \varepsilon) : q \in Q \text{ and } X,Y \in \Gamma_\varepsilon \} $

$\delta'([(q,X),(p,Y),(r,Z)], a, \varepsilon) = \{([(q,X),\delta(p,a,Y), \delta(r,b,Z)], \varepsilon): X,Y,Z \in \Gamma_\varepsilon\ \text{ and } b \in \Sigma\} $

The first component of a state in $Q'$ records the guessed state $q$ and does not change once it is initially recorded. The second element records what state we are in after having processed some prefix of the input x, starting from state $q_0$, and the third element records what state we are in after having processed some prefix of the guessed $y$, starting from $q$.

I am not sure if this proof works, because I am a bit confused as to what to do with the stack for $M'$.

$\endgroup$
  • $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Nov 3 '14 at 1:13
  • $\begingroup$ Well, I suspect that an automaton recognizing FH(L) wouldn't require any more memory than one recognizing L. $\endgroup$ – David Smith Nov 3 '14 at 1:14
  • $\begingroup$ Have you tried to prove your suspicion? Where did you get stuck? $\endgroup$ – Yuval Filmus Nov 3 '14 at 1:15
  • $\begingroup$ I'll write my proof attempt as an answer, so you can comment. $\endgroup$ – David Smith Nov 3 '14 at 1:19
  • $\begingroup$ "I am not sure if this proof works, because I am a bit confused as to what to do with the stack for $M'$" – that's the crux of the problem, and leads me to believe that there is some counterexample, though I couldn't think of any. The problem is that you need to simulate $M$ while at the same time counting how many symbols you have seen and how many more to go. $\endgroup$ – Yuval Filmus Nov 3 '14 at 3:35
7
$\begingroup$

The intuition developed in the comments is right. The answer is NO, there is a counter-example, a CFL for which the first halves are not CFL.

$L = \{ a^m b^n c^n a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c\}$, from the answer on our sister site.

Proof by Pumping lemma: pick $a^p b^p c^p \in \mathrm{FH}(L)$; pumping either destroys the "$b^n c^n$"- or the "first half"-property.

A slight adaptation of that language is $K = \{ a^m b^n c^n \#\# a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c,\#\}$. We can now "force" the point where the cutting site of the first half is and get another proof technique.

Let $H = FH(K) \cap a^*b^*c^*\#$. This means we only consider first halves where the middle is exactly at the point between the two $\#$-symbols. Thus. $m+2n+1=1+3m$, or $m=n$. Thus $H=\{a^nb^nc^n \mid n\ge 1\}\#$. Now if $K$ is context-free then $H$ is context-free (via the closure property intersection by regular languages). This language is close to a standard non-context-free example $\{a^nb^nc^n \mid n\ge 1\}$. This in turn can be obtained by right quotient with $\#$ which also preserves context-freeness.

$\endgroup$
  • $\begingroup$ I added the proof idea (taken from the source linked at Mathematics so that the value of this answer does not depend on these resources' availability. $\endgroup$ – Raphael Nov 4 '14 at 6:53
  • $\begingroup$ @Raphael Thanks. I added a text to explain the specific use of the additional $\#$-character that I introduced. $\endgroup$ – Hendrik Jan Nov 4 '14 at 12:50
  • $\begingroup$ Ah, now I see where you were going with that. Nice! $\endgroup$ – Raphael Nov 4 '14 at 16:31

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.