0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hint: is the set of all Turing machines countable? $\endgroup$
    – Tom van der Zanden
    Jan 11, 2015 at 18:13

1 Answer 1

Reset to default
0
$\begingroup$

(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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ You could improve your answer by adding your reasoning. $\endgroup$
    – Tom van der Zanden
    Feb 15, 2015 at 21:21
  • $\begingroup$ For (b), your reasoning is insufficient as is. HINT: think about (c). $\endgroup$
    – Ran G.
    Feb 15, 2015 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.