(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
