Rice theorem :
1. Any non-trivial property of the LANGUAGE recognizable by a Turing machine is undecidable.
2. Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable
While solving please describe non-trivial/trivial and non-monotonic /monotonic property of particular statement .
Which of the following problems are undecidable?
- Membership problem in context-free languages.
- Whether a given context-free language is regular.
- Whether a finite state automation halts on all inputs.
- Membership problem for type 00 languages.