1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A context free language is a fortiori a context sensitive language. $\endgroup$ – Yuval Filmus Oct 11 '15 at 7:04
  • 3
    $\begingroup$ 1) "I understand that this is because" -- that not a valid conclusion. The claim is not that CFL is not closed against this operation, but a characterisation of RE. 2) Note that since CFL $\subset$ CSL $\subset$ R $\subset$ RE your question, read literally, is ill-posed. Is your real question if there are $L_1$, $L_2$ and $h$ so that $h(L_1 \cap L_2) \not\in$ CSL? $\endgroup$ – Raphael Oct 11 '15 at 7:20
  • $\begingroup$ Thank you for the comments and advices. Sorry I'm yet to understand the meaning of 'a fortiori' in the comment and also about characterization of RE. For 2), yes, with addition that $L_1, L_2 \in CSL$. But I am also become interested in $h(L_1 \cap L_2)$ no matter what languages $L_1, L_2$ are, after reading your comment. Thank you also for editing. $\endgroup$ – kate Oct 11 '15 at 19:05
4
$\begingroup$

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.

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