[Solved]: Does applying a homomorphism to the intersection of two CSLs yield RE languages?

Problem Detail: 

For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L_1$ and $L_2$ such that $L = h(L_1 \cap L_2)$.

I understand that this is because context-free languages are not closed under intersection so $L_1 \cap L_2$ will produce non-context-free languages. Since context-sensitive grammars doesn't allow erasing rules which context-free grammars allow to, then the language must be recursively enumerable language. Then recursively enumerable languages are closed under homomorphism.

If $L_1$ and $L_2$ are context-sensitive languages, does $L = h(L_1 \cap L_2)$ still result in $L \in L(RE)$, as context-sensitive languages do closed under intersection but not morphisms?

Asked By : kate

Answered By : Raphael

This follows from closure properties of CSL: it's closed against intersection and $\epsilon$-free homomorphism, but not against (general) homomorphism.

Thus, $h(L_1 \cap L_2)$ is always context-sensitive if $h$ is $\epsilon$-free.

If $h$ is not, $h(L_1 \cap L_2)$ may not be. As an example, take $L_1$ and $h$ from the proof that CSL is not closed against general homomorphism, and $L_2 = \Sigma^*$.

Since CSL $\subseteq$ RE and RE is closed against intersection as well as (general) homomorphism, $h(L_1 \cap L_2)$ is indeed always in RE.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48104

3.2K people like this

 Download Related Notes/Documents