Decision Properties in Theory of Computation: DFA Tests, CFG Boundaries and Turing Machine Undecidability

A learner may memorise membership, emptiness, finiteness, equivalence and universality as decision properties yet miss that the answer changes for a DFA, CFG or Turing machine. Use an algorithm-first method: identify the representation, ask whether a halting procedure exists, then choose reachability, a product construction, a grammar algorithm or an undecidability reduction. We apply it to an exact two-DFA product and an exact A_TM reduction using fixed input 0110.

See related topics in CS Fundamentals.

1. Decision properties begin with a YES/NO question and a representation

A decision problem asks whether an instance belongs to a set. Its decider must halt with YES or NO. A recogniser accepts members but may loop on a NO instance.

Standard questions are:

• Membership: is w in L?

• Emptiness: is L = ∅?

• Finiteness: is |L| finite?

• Universality: is L = Σ*?

• Equivalence: is L1 = L2?

• Inclusion: is L1 ⊆ L2?

• Disjointness: is L1 ∩ L2 = ∅?

Always name the representation. Emptiness is decidable for a DFA and a CFG, but undecidable for a general Turing-machine recogniser. Closure may provide a decider's construction, but is not itself a decision property.

2. Regular-language tests reduce to finite graph search

For a DFA, membership follows the unique transition sequence and checks the final state. Emptiness asks whether an accepting state is reachable. Finiteness asks whether a reachable cycle can reach an accepting state. Universality complements a complete DFA and tests emptiness. Disjointness builds a product for intersection, then tests reachability.

Two transformations handle comparisons:

• L(A) ⊆ L(B) exactly when L(A) ∩ complement(L(B)) is empty. A bad product state has A accepting and B rejecting.

• L(A) = L(B) exactly when their symmetric difference is empty. A mismatch state has exactly one accepting component.

Before complementing an incomplete DFA, add an explicit dead state for every missing transition; swapping accepting and rejecting states alone is invalid. Breadth-first search terminates because the product has finitely many states.

3. Worked DFA product: inclusion is true, equivalence is false

Let Σ = {0,1}. DFA A recognises strings ending in 01. Its states are {a0,a1,a2}, its start is a0, and only a2 accepts.

DFA B recognises strings containing 01. Its states are {b0,b1,b2}, its start is b0, and only b2 accepts.

Starting at (a0,b0), breadth-first search gives exactly five reachable product states:

For inclusion, a bad state would be (a2,b0) or (a2,b1). Neither is reachable, so L(A) ⊆ L(B). This agrees with the language meaning: every string ending in 01 contains 01.

Equivalence fails because (a1,b2) and (a0,b2) are mismatch states. The shortest witness is 010:

(a0,b0) --0--> (a1,b1) --1--> (a2,b2) --0--> (a1,b2)

Thus 010 is accepted by B because it contains 01, but rejected by A because it does not end in 01.

4. Emptiness and finiteness ask different reachability questions

Consider DFA C over {a,b}. Its states are {q0,q1,q2,qd}, its start is q0, and only q2 accepts. The transitions are q0: a->q1, b->qd; q1: a->q1, b->q2; q2: a->q1, b->qd; and qd: a->qd, b->qd.

ab proves non-emptiness: q0 --a--> q1 --b--> q2. The worked string aaab follows q0 --a--> q1 --a--> q1 --a--> q1 --b--> q2.

The language is also infinite: the reachable loop q1 --a--> q1 can reach q2 on b, so every a^n b for n >= 1 is accepted. The loops at qd prove nothing about infinitude because qd cannot reach an accepting state.

5. CFG properties have an algorithmic core and an undecidable boundary

CFG membership is decidable, for example by CYK after conversion to Chomsky normal form. For emptiness, mark variables that derive terminal strings and test whether the start variable is productive. For finiteness, reduce the grammar and test whether productive recursion creates unbounded terminal yield.

Use the grammar S -> AB | epsilon, A -> aA | a, B -> b. It generates aaab as follows:

S => AB => aAB => aaAB => aaaB => aaab

S => epsilon makes the language non-empty. The rule A -> aA can add arbitrarily many a symbols before A -> a, generating {a^n b | n >= 1} plus epsilon, so the language is infinite.

At the boundary, equivalence, inclusion, universality and regularity are undecidable for an arbitrary CFG. Emptiness of the intersection of two CFLs, hence general disjointness for two CFGs, is also undecidable. Non-closure under intersection does not by itself prove undecidability.

6. Turing-machine properties: Rice's theorem and an exact reduction

Define the undecidable language A_TM = {<M,w> | M accepts w}. On a non-member, M may reject or loop. Turing Machines and Decidability: Halting Problem Proof explains that distinction.

Rice's theorem says every non-trivial semantic property of a TM-recognised language is undecidable. Emptiness depends only on L(M); some machines recognise ∅ while others recognise a non-empty language. Thus E_TM = {<M> | L(M) = ∅} is undecidable. Rice's Theorem for GATE: Two-Part Undecidability Test develops both checks.

From <M,0110>, construct N over {0,1}. On any x, it simulates M on fixed string 0110. If M accepts, N accepts x; if M rejects, N deliberately loops; if M loops, so does the simulation.

• If M accepts 0110, then L(N) = {0,1}*, so an E_TM decider would answer NO.

• If M does not accept 0110, then L(N) = ∅, so that decider would answer YES.

Inverting the answer decides A_TM, a contradiction. Thus A_TM <=m complement(E_TM); decidable languages have decidable complements.

Rice does not cover every TM question. “Does M have seven states?” is decidable from the encoding. “Does M halt on every input?” is undecidable but is not solely a property of L(M), so Rice does not directly prove it.

7. How exam-style questions test the boundary

Typical tasks are to classify a property for a representation, build a product, classify a CFG property, distinguish acceptance from halting, apply Rice, or read a reduction's direction.

Remove these common traps:

• A ⊆ B means search for B-accept and A-reject. Correction: search for A-accept and B-reject.

• Any DFA cycle proves an infinite language. Correction: the cycle must be reachable and able to reach an accepting state, unlike the loops at qd.

• Recognisable means decidable. Correction: a recogniser may loop on a NO instance.

• Rice applies to every statement about a TM. Correction: it applies directly only to non-trivial semantic properties of the recognised language.

• The constructed N detects whether M loops. Correction: N simply follows the simulation forever.

On scratch paper, name the representation, choose a construction or known language, then justify termination or contradiction. KnowledgeGate has over 50 published practice questions in the Decision Properties branch. That indicates practice availability, not exam frequency.

8. Decision properties: the short version and the next step

• Representation controls decidability.

• DFA tests become finite reachability or product searches.

• For CFGs, membership, emptiness and finiteness are decidable, but several comparisons are not.

• For TM-recognised languages, Rice's theorem settles every non-trivial semantic property.

The checkpoints: no reachable (a2,b0) or (a2,b1) proves L(A) ⊆ L(B), while the reduction makes L(N) either {0,1}* or ∅. Continue with Theory Of Computation / Automata Theory, or use ZERO TO HERO only if rebuilding several CS subjects. Reconstruct the five product states and both reduction outcomes without looking.