Question

Consider the following statements :
A. Membership problem is decidable for regular and CFL languages.

B. Emptiness problem is undecidable for RE languages

C. Finiteness problem is decidable for regular languages

D. Equivalence problem is decidable for context-free and RE languages

Choose the correct answer from the options given below :

• A. A, B, C only
• B. B, C, D only
• C. C, D, A only
• D. A, B only

Hint:

Regular languages are the most "well-behaved" as almost all their basic properties are decidable. Once you move to RE languages, Rice's Theorem makes almost everything undecidable!

Answer 1

The Correct Option is A

To solve this, we must examine the decidability properties for different classes of languages within the Chomsky hierarchy. 1. Evaluating Statement A: The membership problem asks whether a given string $w$ belongs to a language $L$. For regular languages, this is decidable using a Deterministic Finite Automaton (DFA). For Context-Free Languages (CFL), it is decidable using algorithms such as the CYK algorithm. Thus, A is correct. 2. Evaluating Statement B: The emptiness problem asks if a language $L$ is empty ($L = \emptyset$). For Recursively Enumerable (RE) languages, any non-trivial property of the language is undecidable according to Rice's Theorem. Since emptiness is a non-trivial property, it is undecidable for RE languages. Thus, B is correct. 3. Evaluating Statement C: The finiteness problem asks if a language $L$ contains a finite number of strings. For regular languages, we can check for the existence of cycles in the corresponding DFA that can reach an accepting state. If no such cycle exists, the language is finite. Thus, C is correct. 4. Evaluating Statement D: The equivalence problem asks if two languages are identical ($L_1 = L_2$). This problem is undecidable for Context-Free Languages. It is also undecidable for RE languages. Therefore, the claim that it is decidable is incorrect. Since statements A, B, and C are true, Option (1) is the correct answer.