# Which closure properties are always valid between regular, context-free and non context-free languages?

I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. Below you can see my scheme.

I am trying to find all possible internal closure properties of these different languages that will always be valid. E.g., I know that $$\text{Regular language } \cup \text{ CFL } = \text{ CFL }$$

$$\text{Regular language } \cap \text{ CFL } = \text{ CFL }$$ $$\text{Regular language } ^* \text{ CFL } = \text{ CFL }$$

What other internal properties are there between these languages?

• Asking for all possible closure properties -- or asking for all "internal properties" (whatever that is) -- seems too broad to me. Any community votes on that? I suggest you consult closure-properties and en.wikipedia.org/wiki/Regular_language#Closure_properties and en.wikipedia.org/wiki/Context-free_language#Closure and math.stackexchange.com/q/1443162/14578, then see if there is anything not already covered by those and whether you have any specific question. – D.W. Dec 31 '20 at 7:59
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Usually what works better is to ask about a specific conceptual issue you're uncertain about. – D.W. Dec 31 '20 at 8:00
• @D.W. How is this a "yes/no" question? I am clearly asking for the internal properties between these different languages. Online, you can only find the closure properties for each language, but you can't find the properties between them. Therefore, I think your arguments don't suffices enough. – NimaJan Dec 31 '20 at 10:36
• It looks to me like the post has two questions: (a) is my table correct?, and (b) what other "internal properties" are there?. (a) is a check-my-answer, and (b) looks like it might be too broad to me. Perhaps the community will be OK with the question; that's up to them. – D.W. Dec 31 '20 at 20:59

Assume that $$\mathcal K$$ and $$\mathcal L$$ are two families of languages with $$\mathcal K\subset \mathcal L$$ such that $$\mathcal L$$ is closed under the operation $$\circ$$. Then for $$K\in\mathcal K$$ and $$L\in \mathcal L$$ we have $$K\circ L\in \mathcal L$$.
This is obvious, as both $$K,L\in \mathcal L$$. Usually we can choose simple examples that we can't do better. For instance, choose a "difficult" language in $$\mathcal L$$, so $$L\in \mathcal L \setminus \mathcal K$$. Then $$L=\varnothing \cup L$$, $$L=\Sigma^*\cap L$$, and $$L=\{\lambda\}\cdot L$$ show that we cannot do better than $$\mathcal L$$.