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

Learn an algorithm-first way to classify membership, emptiness, finiteness, inclusion, equivalence and universality for DFAs, CFGs and Turing machines.

KnowledgeGate Team

Exam prep & CS education

Updated 29 Sep 20266 min read
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. The method is concrete: an exact two-DFA product and an exact A_TM reduction using fixed input 0110.

See related topics in CS Fundamentals.

For the earlier DFA-only treatment, see Decidability Basics: DFA Tests and Limits; this post extends the decision-property comparison to CFG algorithms and Turing-machine undecidability.

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 = empty set?

  • Finiteness: is |L| finite?

  • Universality: is L = Sigma*?

  • Equivalence: is L1 = L2?

  • Inclusion: is L1 subseteq L2?

  • Disjointness: is L1 intersection L2 = empty set?

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.

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) subseteq L(B) exactly when L(A) intersection 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 Sigma = {0,1}. DFA A recognises strings ending in 01. Its states are {a0,a1,a2}, its start is a0, and only a2 accepts.

State in A

On 0

On 1

a0

a1

a0

a1

a1

a2

a2

a1

a0

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

State in B

On 0

On 1

b0

b1

b0

b1

b1

b2

b2

b2

b2

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

Product state

On 0

On 1

(a0,b0)

(a1,b1)

(a0,b0)

(a1,b1)

(a1,b1)

(a2,b2)

(a2,b2)

(a1,b2)

(a0,b2)

(a1,b2)

(a1,b2)

(a2,b2)

(a0,b2)

(a1,b2)

(a0,b2)

For inclusion, a bad state would be (a2,b0) or (a2,b1). Neither is reachable, so L(A) subseteq 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.

Two DFA transition tables feed a five-state product graph; the highlighted path 010 reaches a symmetric-difference state, proving inclusion but not equivalence.

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 empty set while others recognise a non-empty language. Thus E_TM = {<M> | L(M) = empty set} 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) = empty set, 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.

A reduction maps input <M,0110> to machine N; acceptance yields a universal language, while non-acceptance yields the empty language and inverted answers.

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 subseteq 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. The Decision Properties branch also offers practice questions. Use them to test the constructions and distinctions here, not to infer 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) subseteq L(B), while the reduction makes L(N) either {0,1}* or empty set. Continue with Theory Of Computation / Automata Theory as a structured next step. Reconstruct the five product states and both reduction outcomes without looking.