Examples of Decidable Problems
You'll learn: Concrete examples of problems that always have a yes/no algorithmic answer, including DFA acceptance, CFG membership, and basic arithmetic.
What Makes a Problem Decidable?
A problem is decidable if there exists a Turing Machine (or algorithm) that always halts and correctly answers "yes" or "no" for every input. Let's examine some classic decidable problems you've already encountered.
Testing DFA Acceptance
Problem: Given a DFA and a string, does the DFA accept the string?
This is decidable! You simply simulate the DFA step-by-step through the string. Since DFAs always halt (they process each symbol exactly once), you'll always get a definite answer. Think of it like following GPS directions—you'll always know whether you end up at the right destination.
Algorithm: Start in the initial state, follow transitions for each symbol, and check if you end in an accepting state.
Testing CFG Membership
Problem: Given a context-free grammar and a string, does the grammar generate the string?
This is also decidable! You can use the CYK parsing algorithm (which you've learned). Convert the grammar to Chomsky Normal Form and run CYK—it always terminates and tells you definitively whether the string belongs to the language.
Why it works: CYK has a bounded runtime based on string length—no infinite loops possible.
Arithmetic Problems
Problem: Given an arithmetic expression like "17 + 25 = 42," is it true?
Absolutely decidable! You evaluate the expression using standard algorithms, which always terminate and give a clear answer. Arithmetic operations on integers are well-defined and computable.
Key Takeaway: Decidable problems include DFA acceptance (always halts via simulation), CFG membership (CYK algorithm guarantees termination), and arithmetic evaluation—all have algorithms that always halt with a correct yes/no answer.