1,858 views

2 Answers

3 votes
3 votes

The statement is false because we know that sigma star is countable and a language is nothing but a subset of sigma star..every subset of a countable set is countable..hence all languages are countable.

Hence every language whether it is RE or not ,it is always countable.So the statement is false.

Not RE will always be countable infinite.

0 votes
0 votes

False, as there are both countably and uncountably infinite languages which don’t fall under RE
This question is analogous to asking are all countably infinite languages RE? Whose answer is NO for the exact reason that non-RE languages can also be countably infinite.

edited by

Related questions

1 votes
1 votes
1 answer
2
1 votes
1 votes
0 answers
4
sanket03 asked Dec 18, 2018
179 views
Can someone tell me if countability topic from toc is still in syllabus of gate 2019 or not