HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#89082, answer score: 6

Revisions (0)

No revisions yet.