Given ∑ = {a, b}, which of the following sets is not countable ?
1997
Given ∑ = {a, b}, which of the following sets is not countable ?
- A.
Set of all strings over ∑
- B.
Set of all languages over ∑
- C.
Set of all regular languages over ∑
- D.
Set of all languages over ∑ accepted by Turing machines
Attempted by 4 students.
Show answer & explanation
Correct answer: B
Strings: Any individual string is finite, and the collection of all strings (Σ*) is countably infinite.
Languages defined by machines/grammars: Any language that can be parsed or recognized by a machine (Regular, Context-Free, Decidable, or Turing-Recognizable) requires a finite system of rules to define it. Since the number of distinct machines we can build is countable, the number of such languages is also countable.
All possible languages: The set of all languages (2Σ*) includes entirely arbitrary collections of strings that don't follow any algorithmic pattern or machine rules. This maps directly to an uncountable power set.
Therefore, the set of all languages over Σ is the only uncountable set in the list.
Correct Answer: B