Decidable Problem
- If there is a Turing machine that decides the problem, called as Decidable problem.
- A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps.
- A problem is decidable, if there is an algorithm that can answer either yes or no.
- A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps.
- Decidable problem is also called as totally decidable problem, algorithmically solvable, recursively solvable.
Undecidable Problem (Semi-dedidable or Totally not decidable)
- A problem that cannot be solved for all cases by any algorithm whatsoever.
- Equivalent Language cannot be recognized by a Turing machine that halts for all inputs.
The following problems are undecidable problems:
- Halting Problem: A halting problem is undecidable problem. There is no general method or algorithm which can solve the halting problem for all possible inputs.
- Emptyness Problem: Whether a given TM accepts Empty?
- Finiteness Problem: Whether a given TM accepts Finite?
- Equivalence Problem: Whether Given two TM’s produce same language?. Is L(TM1) = L(TM2) ?
- Is L(TM1) ⊆ L(TM2) ? (Subset Problem)
- Is L(TM1) Ո L(TM2) = CFL?
- Is L(TM1) = Σ* ? (Totality Problem)
- Is the complement of L(G1) context-free ?
- Semi decidable: A problem is semi-decidable if there is an algorithm that says yes. if the answer is yes, however it may loop infinitely if the answer is no.
- Totally not decidable (Not partially decidable): A problem is not decidable if we can prove that there is no algorithm that will deliver an answer.
Decidability table for Formal Languages:
Problems | RL | DC | CFL | Rec | RE |
Membership | Y | Y | Y | Y | N |
Finiteness | Y | Y | Y | N | N |
Emptiness | Y | Y | Y | N | N |
Equivalence | Y | Y | N | N | N |
Is L1 ⊆ L2 ?(SUBSET) | Y | N | N | N | N |
Is L = REGULAR? | Y | Y | N | N | N |
Is L Ambiguous? | Y | N | N | N | N |
L=∑* ?(UNIVERSAL) | Y | Y | N | N | N |
L1 ∩ L2= Ф ?(DISJOINT) | Y | N | N | N | N |
Is L= Regular? | Y | Y | N | N | N |
L1 ∩ L2= L | Y | N | N | Y | Y |
Is L' also same type? | Y | Y | N | Y | N |
Notes : RL= Regular Language , DC = Deterministic context-free languages (DCFL), CFL= Context Free Languages (CFL), Rec = Recursive language, RE= Recusively Enumerable Language.
You can follow the detailed champion study plan for GATE CS 2021 from the following link:
Detailed GATE CSE 2021 Champion Study Plan
Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:
Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)
Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:
Click here to avail Online Classroom Program for Computer Science Engineering
Thanks
The Most Comprehensive Exam Prep App!
Download BYJU'S Exam Prep, Best gate exam app for Preparation
Comments
write a comment