Discussion
For Σ to be an alphabet and L ⊆ Σ* be a language A is said to be decidable if there exists a Turing machine M for every string ω ∈ Σ* with which of the following conditions.
(i) If ω ∈ L, the computation of TM M on input string ω terminates in accept state
(ii) If ω ∉ L (ω does not belong to L) then computation of TM M on input string ω terminates in reject state
(iii) If ω ∈ L then computation of TM M on input string ω terminates in reject state.
Answer: C
The conditions are (i) and (ii) only.
A language L is decidable if some Turing machine M halts on every input and gives the right verdict: for every string \(\omega\) in L, M halts in its accept state (i), and for every string not in L, M halts in its reject state (ii). Halting on both kinds of input is what separates decidable from merely recognisable (recursively enumerable) languages.
Condition (iii) says that strings in L are rejected, which contradicts (i) and would make M decide some other language. Every option containing (iii) is therefore wrong.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development