in Theory of Computation
163 views
0 votes
0 votes
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.
in Theory of Computation
163 views

2 Comments

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.
2
2
OK,its clear now.
0
0

Please log in or register to answer this question.

Related questions