Consider the properties of recursively enumerable sets:
A. Finiteness
B. Context Freedom
C. Emptiness
Which of the following is true?

Correct option is D

Given Properties:
(A) Finiteness: Whether a recursively enumerable set is finite.
(B) Context Freedom: Whether a recursively enumerable set is generated by a context-free grammar.
(C) Emptiness: Whether a recursively enumerable set is empty.
We need to determine which of these properties are undecidable for recursively enumerable sets.
Step 1: Understanding the Decidability of the Properties
1. Finiteness (A):
· Determining whether a recursively enumerable (RE) set is finite is undecidable.
· RE sets can be infinite and generated by algorithms that do not terminate, making this problem undecidable.
2. Context Freedom (B):
· Checking if a recursively enumerable set is generated by a context-free grammar is undecidable.
· This is due to the complexity of matching RE sets to context-free grammars.
3. Emptiness (C):
· For recursively enumerable sets, determining if a set is empty is undecidable.
· Although semi-decidable, if the set is empty, the algorithm cannot decide conclusively in all cases.
Step 2: Analyze the Options
All (A), (B), and (C) are undecidable, as explained above.
Information Booster
1. Recursively Enumerable (RE) Sets:
· A set is recursively enumerable if there exists a Turing machine that enumerates its elements.
· It is not necessary for the Turing machine to halt for non-elements of the set.
2. Key Properties of RE Sets:
· Decidable (Recursive): Problems where an algorithm exists to determine membership conclusively for all inputs.
· Semi-Decidable: Problems where an algorithm can confirm membership but may fail to terminate for non-membership.
3. Examples of Undecidable Problems:
· Halting Problem.
· Equivalence of two RE languages.
· Membership problem for certain types of grammars.
Additional Knowledge
· Context-Free Languages (CFLs): A subset of recursively enumerable languages that are decidable and generated by context-free grammars.
· Undecidability in RE Sets: Extends to most non-trivial properties due to the inherent limitations of Turing machines.