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. Himanshu555 asked Aug 5, 2022 Himanshu555 169 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Kabir5454 commented Aug 5, 2022 reply Follow Share 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 votes 2 votes Himanshu555 commented Aug 5, 2022 reply Follow Share OK,its clear now. 0 votes 0 votes Please log in or register to add a comment.