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?

Improve this question
$\endgroup$
3
  • $\begingroup$ A context free language is a fortiori a context sensitive language. $\endgroup$ Commented Oct 11, 2015 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$ Commented Oct 11, 2015 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$ Commented Oct 11, 2015 at 19:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.