Exams › GATE › Technical

Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable?

1. S1 and S2
2. S3 and S4
3. S2 and S3
4. S1 and S4

Correct answer: S3 and S4

Solution

S3, the set of all languages over the alphabet {0,1}, is uncountable because it includes all possible subsets of strings formed from that alphabet, which corresponds to the power set of the natural numbers. S4, the set of all non-regular languages, is also uncountable since it contains infinitely many languages that cannot be described by finite automata, further contributing to the uncountability.

Related GATE Technical questions

• A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
• Which one of the following kinds of derivation is used by LR parsers?
• In 16-bit 2’s complement representation, the decimal number −28 is:
• Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2^(n−1) II. |A| = ∑(k=1 to n) k C(n,k) Which of the above statements is/are TRUE?
• Which one of the following is NOT a valid identity?
• If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

⚔️ Practice GATE Technical free + battle 1v1 →