6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. I had no idea that context-free languages were so inexpressive. What I was after was a demonstration that there was no natural way to make the language of all, say, PA proofs context-free. I am surprised the demonstration was so easy. $\endgroup$ – Ghwosque Mar 9 '18 at 15:51
6
$\begingroup$

This is a form of left quotient of a context-free language by a regular language:

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

Context-free languages are closed under quotient by regular languages. Usually one considers right quotient, where the regular language is chopped off from the right. The argument however is symmetric (context-free and regular languages are both closed under mirror image).

See

|cite|improve this answer
$\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.