Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Let ∑ be a finite non-empty alphabet and let 2∑* be the power set of ∑*. Which one of the following is TRUE?
    1. Both 2∑* and ∑* are countable
    2. 2∑* is countable and ∑* is uncountable
    3. 2∑* is uncountable and ∑* is countable
    4. Both 2∑* and ∑* are uncountable
Correct Option: C

∑* is countabily finite 2∑* is power set of ∑*
The powerset of countabily infinite set is uncountable
∴ 2∑* is uncountable and ∑* is countable.



Your comments will be displayed only after manual approval.