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

Concept:
• Decidability refers to whether a problem can be solved by a Turing machine in a finite amount of time.
• Different classes of languages (Regular, CFL, CSL, RE) have different decidability properties for common questions like Membership, Emptiness, and Equivalence.

Step 1: Evaluate Statement A (Membership)
For Regular languages, we can simply run the string through a DFA. For CFLs, we can use the CYK algorithm or a PDA. Both are guaranteed to terminate. Thus, A is correct.

Step 2: Evaluate Statement B (Emptiness for RE)
Determining if a Recursively Enumerable (RE) language is empty is equivalent to determining if a Turing Machine accepts no strings. This is a variation of the Halting Problem and is undecidable. Thus, B is correct.

Step 3: Evaluate Statement C (Finiteness for Regular)
For a Regular language (DFA), we can check if there is a cycle in the state transition graph that is reachable from the start state and can reach a final state. This is an algorithmic check. Thus, C is correct.

Step 4: Evaluate Statement D (Equivalence for CFL/RE)
Equivalence is undecidable for Context-Free Languages (one cannot even decide if two CFGs generate the same language). It is also undecidable for RE languages. Thus, D is incorrect.