Undecidability

Question

Which of the following is undecideable?

If a lang. L is CFL, then it's compliment is also a CFL.

If a lang. L is Rec, then it's compliment is also a Rec.

Comments

2. If a lang. L is Rec, then it's compliment is also a Rec. - decidable.( since it is closed under complementation)

1. If a lang. L is CFL, then it's compliment is also a CFL. - should be undecidable ( since CFL is not closed under complementation).

But if L is DCFL- then should be decidable.

---

Here my doubt is if any lang is closed under some operation and whether it's decide or not...I mean both r diferent.

here a lang is decideable....In what sense they are asking.

Will u plz clarify...

Answer 1

First of all let me explain what is the relevance of closure properties with decidability issue.

We say a problem is decidable if we can answer to that problem with surety whether the problem can be solved or not .In other words algorithm exist or not.The problem in this context is about closure properties.

So given closure property of a language we say a particular operation is decidable if that particular set of language is closed under that operation.This is so because if the  language is closed under that operation , we can say with surety that any other language which is obtained by doing the concerned operation on the original language will also result in the same class of language.As an example , we know recursive language is closed under complementation.By saying , we are ensured that complement of a recursive language is also a recursive language.So we have a definite answer and the answer is "yes" to the question :

Is complement of recursive language recursive ??

Now if a language does not satisfy under a given operation , we are not ensured that after applying that operation on that particular language , the resultant language will fall in same class of language.So , for example CFL languages are not closed under complement.So we cannot say with surety that the complement of a CFL will be CFL always.It may or may not be.

In this context hence it is an undecidable issue whether given a language which is a CFL , the complement  will also be a CFL.It may or may not be.

It also follows from Rice's theorem of undecidability which says :

Rice's theorem: Any nontrivial property about the language recognized by a Turing machine is undecidable.

So by non trivial here we mean property (like here complementation property of CFL) which is not closed for CFL language.Trivial properties are those which are in line with closure property of a class of language like complement property for recursive language.

Comments

a set of Language is closed under a operation means applying the operation between any two languages of the set it should be belong to the same set of Language itself.

i mean to say, if a Regular language is closed under Union operation, then the resultant Language by applying the union between any two Regular language is also a Regular Language.

Closed ==> we always guarantee that what is the output ===> Decidable.

 

What about not closed operations ?

We all know that, Regular languages are not closed under Subset operation.

that means, Subset of a Regular Language may or may not be Regular Language ==> we can't say what is output.

Does this mean it is Undecidable ?

Let take two Regular languages, R$_1$ and R$_2$

Now my question is " is R$_2$ is a subset to R$_1$ ? "

My algorithm says, perform R$_2$ - R$_1$, if Resultant Language is " Empty Language ", then Yes, otherwise NO.

∴ Even though it is not known what is output, But we can definitely decide what is the output for the any two arbitrary Languages of Same set !

Undecidable means, You can't decide !

Simplification from the above discussion is :-

Closed ==> Decidable

Not Closed ===> Some are decidable and some are Undecidable.

Regular languages are not closed under infinite union. Does this mean that deciding if the infinite union of a set of regular languages is regular is undecidable?

My approach is :-

First make the Language L = L(R$_1$) $ \cup$ L(R$_2$) $ \cup$ L(R$_3$) .....

So our task is " is given L is RL ? " ---- By RICE theorem it is undecidable !

But note that " To say something is undecidable, there is no way to say decidable ! ", upto now we seen only one approach which leads to undecidable. Therefore we can't directly say it is undecidable, We have to check is there some other approach which can lead to Decidable ?

 

intuitively what i am thinking is, observe the languages and strings belong to each RL, and think when they combined " is there any relation between them ? if yes, think that relation can be preserved with O(1) auxiliary space, (i.e., can we form a RL ) ? if yes, then YES, else NO " ---- i am deciding ==> Decidable !

@Arjun

sir please check it once !

---

Four first half is correct. But for applying Rice's theorem, it must be a property of recursively enumerable set.

Also, your final intuition - does it work for all inputs?

---

But for applying Rice's theorem, it must be a property of recursively enumerable set.

yes sir, it should be RE set, But infinite union of RL may lead to NON-RE, then we can't apply Rice theorem !

then how to conclude ?

can i say like this " L is RE, then By RICE theorem it is Undecidable, if L is NON-RE, it is directly Undecidable."

So any case it is Undecidable !

 

your final intuition - does it work for all inputs?

i am thinking yes, due to surely we don't have to use any auxiliary space, to accept the strings.