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, 2020 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, 2020 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, 2020 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, 2020 at 20:59

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.