# Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement.

Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special metacharacter “|”. Suppose that every string in $L_1$ contains exactly one metacharacter. Let the left half and right half of a string in $L_1$ denote the part of the string before the “|” and the part after, respectively. Let $L_2$ be the language over $\Sigma$ containing all the right halves of the strings in $L_1$.

Then is membership in $L_2$ decidable? What about if $L_1$ is restricted to be nice in some way? I'm fairly sure there are counterexamples in any case, but I can't find them.

If $$L_1$$ is context-free, then so is $$L_2$$. You can show this easily using closure properties of context-free languages. Let $$\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$$; we assume that $$\Sigma$$ and $$\Sigma'$$ are disjoint. Define a homomorphism $$h\colon \Sigma \cup \Sigma' \cup \{|\} \to \Sigma^* \cup \{|\}$$ by $$h(\sigma) = h(\sigma') = \sigma$$ and $$h(|) = |$$, and a homomorphism $$k\colon \Sigma \cup \Sigma' \cup \{|\} \to \Sigma^*$$ by $$k(\sigma) = \sigma$$ and $$k(\sigma') = k(|) = \epsilon$$. Then $$L_2 = k(h^{-1}(L_1) \cap \Sigma^{\prime\ast} | \Sigma^*).$$ The family of context-free languages is closed under homomorphisms, inverse homomorphisms, and intersection with regular languages, hence $$L_2$$ is context-free as well.
$L_2 = R\backslash L_1 = \{ x\in \Sigma^* : yx\in L_1 \text{ for some } y\in R \}$, where in your case $R= \Sigma^* \mid$.