1
$\begingroup$

I know that if a language class is closed under operation X then the problem is decidable.

for eg: "Intersection of two CSL is CSL"? this problem is decidable because it is already proved that CSL follow intersection closure property.

But what if language is not closed under the operation. for eg: problem: Is intersection of two CFL is CFL or not?

as CFL/DCFL is not closed under intersection. then is this true saying that not following closure opertion implies Undecidable problem?

My approach:This problem is same as saying that "A given CSL is CFL or not?" because intersection of two CFL's is CSL for sure. as every CSL is RE then can we also say this problem as "A RE is CFL or not"? if my last statement is true then by using rice theorem this problem must be undecidable and even not RE.

how to approach these type of question when a language is not closed under the given operation?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Which problem is decidable or not? Make it clear. Also, what do you mean by language is closed under operation X? Perhaps you meant language class? $\endgroup$ – Yuval Filmus Jul 31 '17 at 20:52
2
$\begingroup$

Your approach doesn't work. Try proving it to see that it doesn't work. As a silly example, the set of non-empty regular languages isn't closed under intersection, but given two non-empty regular languages, it is decidable whether their intersection is a non-empty regular language.

However, it is in fact undecidable to decide whether the intersection of two context-free languages (say given as context-free grammars) is context-free, essentially since you can encode the computation of a Turing machine as the intersection of two context-free languages. See Theorem 1 in a writeup of Hendrik Jan (a bit of work is required to get this particular result from the theorem: construct grammars for $L(G_1) \flat \{a^nb^n c^m\}$ and $L(G_2) \flat \{a^nb^mc^m\}$; the intersection of these context-free languages is non-context-free iff $L(G_1) \cap L(G_2)$ is non-empty).

|cite|improve this answer
$\endgroup$
2
$\begingroup$

I don't think closure property implies decidability. Consider r.e. languages and intersection. R.e. languages are closed under intersection, e.g., if $L_1$ and $L_2$ are r.e. languages then $L_1 \cap L_2$ is also r.e. but may be undecidable.

On the other hands, CFLs are not closed under intersection. However, a language which is intersection of two CFLs is not CF but may be decidable. For example $L_1=\{a^ib^ia^j |i,j \geq 1 \}$, $L_2=\{a^ib^ja^j |i,j \geq 1 \}$ are both CF, however $L_1 \cap L_2 = \{ a^ib^ic^i | i,j \geq 1\}$ is not CF, but it is still decidable.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @fae2black please read my question.this is not What I am asking. $\endgroup$ – Reena Kandari Aug 1 '17 at 0:22
  • $\begingroup$ @ReenaKandari Then please state your problem clearly and unambiguously, in set theoretic terms for example. What language/set do you want to prove to be decidable? $\endgroup$ – fade2black Aug 1 '17 at 4:59
  • $\begingroup$ see, I edited the question. and basically I want to ask, the problem "intersection of two CFL is CFL or not?" is decidable or not.As CFL does not follow the closure property under intersection. $\endgroup$ – Reena Kandari Aug 1 '17 at 6:21

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.