[Solved]: Deciding Countability of Languages

Problem Detail: 

Suppose we have given $\Sigma=\{a,b\}$, Which one of the following set is not countable

(a) Set of all languages over $\Sigma$

(b) Set of all regular languages over $\Sigma$

(c) Set of all languages over $\Sigma$ accepted by Turing machine

I've read some techniques to find answer to the question like whether

Is the set of all infinite sequences of some alphabets countable or not

Is the set of all finite non-empty subsets of some alphabets countable or not

But they didn't helped me to answer questions like above. I tried Cantor Diagonalization but it didn't help either. How can we answer such questions.

Asked By : Atinesh

Answered By : Atinesh

(a) Un-Countable

(b) Countable

Regular Language may be finite or infinite. Either case enumeration is possible as it contains pattern. Hence, Set of all regular languages over $\sum$ are Countable.

(c) Countable

Since Language accepted by Turing Machine is Recursively Enumerable languages, As Enumeration is possible. Hence, Set of all languages over $\sum$ accepted by TM are Countable

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37134

 Ask a Question

 Download Related Notes/Documents