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

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
winL?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.
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) subseteq L(B)exactly whenL(A) intersection complement(L(B))is empty. A bad product state hasAaccepting andBrejecting.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 |
|---|---|---|
|
|
|
|
|
|
|
|
|
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 |
|---|---|---|
|
|
|
|
|
|
|
|
|
Starting at (a0,b0), breadth-first search gives exactly five reachable product states:
Product state | On 0 | On 1 |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.

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
Maccepts0110, thenL(N) = {0,1}*, so anE_TMdecider would answer NO.If
Mdoes not accept0110, thenL(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.

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 Bmeans search forB-accept andA-reject. Correction: search forA-accept andB-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
Ndetects whetherMloops. Correction:Nsimply 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.
Keep learning
Turing Machine Decision Properties MCQs: 12 Solved Questions with Explanations
Solve 12 Turing machine Decision Properties MCQs with explanations of bounded simulation, Rice's theorem, complements, dovetailing and mapping reductions.
Turing Machines in Theory of Computation: Design, Worked Trace and Decidability
A six-state Turing machine for L = {0^n1^n}: built from the seven-tuple, traced move by move on 0011 to XXYY and q_accept, then proved a decider rather than only a recogniser.
Decision Properties MCQs: 10 Solved CFG and PDA Questions
Solve ten Decision Properties MCQs by separating the input model from the property being tested, then checking the relevant algorithm or undecidability result.
Context-Free Grammar MCQs: 11 solved questions on CFG, CFL and PDA
Context-free grammar solved MCQs with explanations: 11 GATE PYQs on CFGs, the Chomsky hierarchy, CFL closure properties, pushdown automata and decidability.





