42 views
How a language which is not recursively enumerable is uncountable,because as we know every language is a subset of sigma(input alphabet) star which is known to be countable?

Please explain I am getting confused in this.

A non recursive enumerable language is always countable as it subset of $\sum ^{*}$ which is countable set and subset of any countable set is also countable.

Set of non RE language is uncountable because we can write ,

Set of all language = set of all RE language $\cup$ set of all non RE language

we know set of all language is uncountable .

Set of all RE language is countable .

So, Set of all non RE language has to be uncountable to make set of all language set uncountable.
OK,its clear now.

1 vote
1
243 views