• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Theory of Computation

Given Sigma = {a, b}, which one of the following sets is not countable? A. Set of all strings over Sigma B. Set of all languages over Sigma C. Set of all regular languages over Sigma D. Set of all languages over Sigma accepted by Turing machines

GATE 1997 · Theory of Computation · Countable Uncountable Set · medium

Answer: The set of all languages over Sigma is NOT countable (it equals the uncountable power set of Sigma*). Answer: B.

  1. Check countability of Sigma* (option A): All strings over {a,b} can be enumerated: epsilon(length 0), a, b (length 1), aa, ab, ba, bb (length 2), ... This is a bijection with natural numbers. So option A is countable.
  2. Check countability of all languages (option B): A language is any subset of Sigma*. The set of all languages = P(Sigma*) (power set). Since Sigma* is countably infinite, by Cantor's theorem, P(Sigma*) is uncountable. Cantor's diagonal argument shows no surjection from N to P(Sigma*) exists. Hence option B is NOT countable.
  3. Check options C and D: Each regular language is recognized by some DFA. DFAs are finite structures and can be encoded as finite strings, so there are only countably many DFAs, hence countably many regular languages (option C is countable). Similarly, each TM is finitely encodable, so option D (TM-recognized languages = recursively enumerable languages) is also countable.