![GATE 2014 [Set-3]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
GATE 2014 [Set-3]
April 4, 2025GATE 2014 [Set-3]
April 4, 2025GATE 2014 [Set-3]
| Question 26 |
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE?
| Both 2Σ* and Σ* are countable | |
| 2Σ* is countable and Σ* is uncountable | |
| 2Σ* is uncountable and Σ* is countable | |
| Both 2Σ* and Σ* are uncountable |
Question 26 Explanation:
If = {0,1} then Σ* = {ϵ, 0, 1, 00, 01, 10, 11, 000, ……………}
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2Σ* is uncountable, it has been already proved by using Diagonalization method.
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2Σ* is uncountable, it has been already proved by using Diagonalization method.
Correct Answer: C
Question 26 Explanation:
If = {0,1} then Σ* = {ϵ, 0, 1, 00, 01, 10, 11, 000, ……………}
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2Σ* is uncountable, it has been already proved by using Diagonalization method.
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2Σ* is uncountable, it has been already proved by using Diagonalization method.