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?

S1 and S2
S3 and S4
S2 and S3
S1 and S4

LohaHridoy

5 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 2 : S3 and S4

Every Recursively enumerable language has a Turing Machine, and a set of all Turing Machine's is countable. Therefore, the set of all Recursively enumerable languages is countable.
There exists a one to one equivalence for all valid C programs and all valid TM encodings. Since the set of all valid TM encodings is countable, it means that the set of all syntactically valid C programs is also countable.
Set of all languages is uncountable and the set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as the union of two countable sets cannot make an uncountable set.

S3 and S4 are uncountable sets.

:

Every TM can be encoded with 0's and 1's, that is, every TM can be represented by a unique binary number.

Σ = {0,1} then set of all binary strings = Σ^∗. Σ^∗ is countable → Set of all TM's is countable.

5 views Answered 2022-09-04 04:29

Related Questions

Consider the following statements for the two non-empty sets A and B: 1) (A ∩ B) ∪ (A ∩ B̅) ∪ (A̅ ∩ B) = A ∪ B 2) (A ∪ (A̅ ∩ B̅)) = A ∪ B Which of the above statements is/are correct?

1 Answers 4 Views

Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?

1 Answers 4 Views

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true I. L̅1 (complement of L1) is recursive II. L̅2 (complement of L2) is recursive III. L̅1 is context-free IV. L̅1 ∪ L2 is recursively enumerable?

1 Answers 5 Views

Language L1 is defined by the grammar: S1 → aS1b|ϵ Language L2 is defined by the grammar: S2 → abS2|ϵ Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?

1 Answers 4 Views

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y̅ reduces to W, and Z reduces to X̅ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

1 Answers 4 Views

Consider the following languages L1 = {ap | p is a prime number} L2 = {anbmc2m | n ≥ 0, m ≥ 0} L3 = {anbnc2n | n ≥ 0} L4 = {anbn | n ≥ 1} Which of the following are CORRECT I. L1 is context-free but not regular. II. L2 is not context-free III. L3 is not context-free but recursive. IV. L4 is deterministic context-free?

1 Answers 5 Views

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable I. Given a regular expression R and a string w, is w ∈ L(R) II. Given a context-free grammar G, is L(G) = ϕ III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑ IV. Given a Turing machine M and a string w, is w ∈ L(M) ?

1 Answers 4 Views

Consider the following languages over the alphabet ∑ = {a, b, c} Let L1 = {an bn cm | m, n ≥ 0} and L2 = {am bn cn | m, n ≥ 0} Which of the following are context-free languages I. L1 ∪ L2 II. L1 ∩ L2?

1 Answers 7 Views

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

1 Answers 4 Views

The points in the graph below represent the halts of a lift for durations of 1 minute, over a period of 1 hour. Which of the following statements are correct i. The elevator never moves directly from any non-ground floor to another non-ground floor over the one hour period ii. The elevator stays on the fourth floor for the longest duration over the one hour period?

1 Answers 6 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)