Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
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 automation halts on all inputs
IV. Membership problem for type 0 languages1
I and IV
2
II and IV
3
III and IV
4
I and II