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 commentRakesh BiswalMar 1, 2017
Manish RawatJul 25, 2017
Eshu YadavSep 29, 2017
choudhurydibarun royDec 28, 2017
Kumar DeepakDec 28, 2017
Kaustubh AgarwalJan 11, 2018
This is one of the mistakes. There are 1-2 more I think.
Ankit BansalJan 21, 2018
AdiTya VerMaJan 23, 2018
Rakesh NamaOct 15, 2019
https://drive.google.com/file/d/1pNE5Bb57sgDWwIxLoaHhOGRVRo7XHHaE/view?usp=drivesdk
ankitaJan 1, 2020