Getting an answer for one chosen input does not make a problem decidable. A decider must return the correct yes or no and halt for every valid input encoding. Membership, emptiness, universality and finiteness reduce to finite-graph tests, while comparing two DFAs uses a product automaton whose shortest separating word here is 10. For the underlying automata notation and practice sequence, use CS Fundamentals for Exams & Placements.
Decidability means a correct answer and guaranteed halting
A decision problem is a set of finite input encodings with a yes-or-no answer. A decider accepts every yes-instance, rejects every no-instance, and halts in both cases. A recogniser may instead loop forever on a non-member.
For DFA membership, the input is a DFA A and string w. Simulate one transition per symbol. After |w| transitions, the machine is in a definite state, so the algorithm halts.
Keep three labels separate. Decidable asks whether an always-halting algorithm exists. Efficient asks about time or memory. Easy in practice also depends on input size and implementation. An exponential algorithm can still prove decidability.
Regular-language properties become finite graph tests
Write a DFA as A = (Q, Sigma, delta, q0, F). Its state set and alphabet are finite, so searches over its explicit transition graph terminate.
Question | Always-halting test | Yes condition |
|---|---|---|
Membership | Simulate | The final state is in |
Emptiness | Search from | No state in |
Universality | Complete, complement, test emptiness | The complement is empty |
Finiteness | Inspect the useful subgraph | It has no directed cycle |
Equivalence | Test symmetric-difference emptiness | No XOR-accepting product state is reachable |
| Test | That language is empty |
Fix DFA A over Sigma = {0,1}. It has states {q0,q1}, start state q0, accepting set {q1}, and transitions:
State | On | On |
|---|---|---|
|
|
|
|
|
|
Thus, A accepts exactly the binary strings ending in 1. On 1010, its path is q0 -> q1 -> q0 -> q1 -> q0, so it rejects. On 1011, it finishes at q1, so it accepts. The language is non-empty because 1 reaches q1. It is not universal because epsilon leaves the machine at non-accepting q0.
Complete and normalise the representation first
NFAs and regular expressions also describe regular languages. Convert them finitely to a DFA before applying these tests. Subset construction can produce up to 2^n DFA states from an n-state NFA. That affects cost, not decidability.
Toggle accepting states only after the automaton is deterministic and complete. If a transition is missing, add a non-accepting sink d, send missing transitions to it, and loop both symbols at d. Toggling NFA final states does not generally produce the complement. Review Finite Automata: DFA vs NFA Explained first.
The pumping lemma can help prove that a language is not regular, but it is not a general classification procedure.
Worked example: equivalence and a shortest witness
Define DFA B over {0,1} with states {p0,p1}, start p0, and accepting set {p1}. State p0 loops on 0 and goes to p1 on 1; p1 loops on both symbols. It accepts strings containing at least one 1.
For L(A) = L(B), construct their symmetric-difference product from (q0,p0). A product state accepts when exactly one component accepts, so the separating states are (q1,p0) and (q0,p1).
Product state | On | On | Separating? |
|---|---|---|---|
|
|
| No |
|
|
| No |
|
|
| Yes |
|
|
| Yes |
Run breadth-first search, trying 0 before 1. At depth 0, (q0,p0) is not separating. At depth 1, 0 returns to the start and 1 reaches (q1,p1), where both accept. Its 0 edge reaches (q0,p1) at depth 2, corresponding to 10.
Thus the languages differ. A rejects 10 because it ends in 0, while B accepts because a 1 occurred. BFS explores by path length, proving no shorter separator exists. The fixed symbol order resolves equal-length choices consistently.
Reuse the product for inclusion, universality and finiteness
For L(A) subseteq L(B), search for a state in F_A x (Q_B - F_B). The only candidate is (q1,p0), and it is unreachable from (q0,p0). Therefore the inclusion is true: every string ending in 1 contains a 1.
For L(B) subseteq L(A), the bad pair is (q0,p1). Input 10 reaches it, so the reverse inclusion is false. The same witness disproves equivalence and identifies exactly which direction fails.
For A, universality is false because its complement accepts epsilon at q0. Finiteness is also false: q1 is reachable, accepting, and lies on the useful cycle q1 --1--> q1. Hence 1, 11, 111, ... are distinct accepted strings. An arbitrary cycle is insufficient. It must be reachable from the start and able to reach an accepting state.
The machine model can change the answer
These tests terminate because a DFA has a finite graph. A similar question about another model need not share the answer. DFA equivalence is decidable through a finite product, while equivalence of arbitrary context-free grammars is undecidable.
A Turing-machine recogniser may accept members and run forever on a non-member, giving no general rejection procedure. Turing Machines and Decidability Explained develops that boundary.
Rice's theorem concerns non-trivial semantic properties of languages recognised by Turing machines. It does not make DFA tests or every syntactic machine property undecidable.
Exam traps and answer-after-attempt drills
Repair these common mistakes:
A recogniser is a decider: demand halting on yes and no inputs.
Exponential means undecidable: separate existence from efficiency.
Toggle NFA final states for complement: determinise and complete first.
Equivalence means product intersection is empty: use symmetric difference.
Any cycle means an infinite language: require a useful reachable cycle.
Different state names or counts mean different languages: compare accepted strings.
One tested string proves equivalence: search the complete product.
The pumping lemma decides regularity: use it as a one-way proof tool.
The four tasks are to (1) run A on 1010, (2) run B on 1010, (3) find the shortest separator, and (4) test both inclusion directions. Answers: A rejects 1010; B accepts 1010; the shortest separator is 10; L(A) subseteq L(B) is true; and L(B) subseteq L(A) is false.
Exam questions commonly ask you to match properties with terminating algorithms, simulate membership, use reachability for emptiness, find a useful cycle, construct a product, produce a shortest separator, or distinguish a decider from a recogniser. Regular Language Properties: Closure and Decision Tests connects these decision procedures with closure arguments and Myhill-Nerode reasoning.
The short version and the next step
Decidability requires a correct answer and halting on every input. DFA membership halts after one transition per symbol, and graph reachability settles several other properties. Complement requires a complete DFA. Equivalence reduces to emptiness of the symmetric difference. Finiteness requires a useful cycle, not just any cycle.
Now reconstruct (q0,p0) --1--> (q1,p1) --0--> (q0,p1) without looking back. Explain why 10 separates the machines and why only L(A) subseteq L(B) remains true. Then use GATE Guidance by Sanchit Sir as a structured preparation route, and repeat the four drills or move to timed practice.
