1
$\begingroup$

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.

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 31 '20 at 7:59
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 31 '20 at 8:00
  • $\begingroup$ @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. $\endgroup$ – NimaJan Dec 31 '20 at 10:36
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 31 '20 at 20:59
2
$\begingroup$

I am afraid that there is no better general result than the obvious one.

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

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