Which of following problems are undecidable? I. Membership problem in…
2020
Which of following problems are undecidable?
I. Membership problem in context-free languages
II. Whether a given context-free language is regular
III. Whether a finite state automaton halts on all inputs
IV. Membership problem for type 0 languages
- A.
III and IV
- B.
I and IV
- C.
I and II
- D.
II and IV
Attempted by 39 students.
Show answer & explanation
Correct answer: D
Correct Answer: D (II and IV)
II is Undecidable: Checking if a context-free language is regular is a well-known undecidable problem (proven via Rice's Theorem or reduction from the Post Correspondence Problem).
IV is Undecidable: Type 0 languages are Recursively Enumerable (RE). The membership problem for $RE$ languages is equivalent to the Halting Problem, which is undecidable.
I & III are Decidable: Membership for CFLs is decidable (CYK algorithm). A Finite State Automaton (DFA/NFA) always halts on all inputs because it processes exactly one input symbol per transition and has no infinite loops without consuming input; hence, its halting problem is trivially decidable.