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'$.