patternMinor
Can the regular image of a context-free language be undecidable?
Viewed 0 times
cantheimageundecidablefreeregularlanguagecontext
Problem
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.
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.
Solution
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 = 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.
Context
StackExchange Computer Science Q#89082, answer score: 6
Revisions (0)
No revisions yet.