Question 23970: Each Recorded Prefix Subset Must Equal All Closed NFA Reachable States

Original question and givens

Use complete epsilon-NFA states=[s19, m19, f19, e119, e219, d19], alphabet=[a19, b19], start=s19, final_states=[f19], transitions=[[s19, null, m19], [s19, null, d19], [m19, a19, m19], [m19, b19, f19], [f19, null, e119], [e119, null, e219]]. Each transition is [from,input symbol or null,to], with null consuming no input. States/labels and transitions must qualify, and subsets are unique carrier subsets sorted lexicographically. Empty alphabet/final sets and empty subset states are allowed. Supplied full input=[a19, a19, a19, b19]. Give (input, DFA_prefix_subsets, direct_NFA_prefix_subsets, prefix_invariant, accepted, certificate, finite_tests_language_equivalence_claim, boundary).

• G001 — Use complete epsilon-NFA states=[s19, m19, f19, e119, e219, d19], alphabet=[a19, b19], start=s19, final_states=[f19], transitions=[[s19, null, m19], [s19, null, d19], [m19, a19, m19], [m19, b19, f19], [f19, null, e119], [e119, null, e219]]. Each transition is [from,input symbol or null,to], with null consuming no input. States/labels and transitions must qualify, and subsets are unique carrier subsets sorted lexicographically. Empty alphabet/final sets and empty subset states are allowed. Supplied full input=[a19, a19, a19, b19]. Give (input, DFA_prefix_subsets, direct_NFA_prefix_subsets, prefix_invariant, accepted, certificate, finite_tests_language_equivalence_claim, boundary).

Definition and scope

Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.

• mko-subset-construction-nfa-to-dfa

Step-by-step derivation

source operation=subsetdfa-full-word-trace-invariant;original snapshot and mathematics retained

explicit ordered source output fields=[input, DFA_prefix_subsets, direct_NFA_prefix_subsets, prefix_invariant, accepted, certificate, finite_tests_language_equivalence_claim, boundary]

ORIGINAL states=[s19, m19, f19, e119, e219, d19],alphabet=[a19, b19],start=s19;ORIGINAL transition order=[[s19, null, m19], [s19, null, d19], [m19, a19, m19], [m19, b19, f19], [f19, null, e119], [e119, null, e219]]

final set normalized UTF16=[f19];states nonempty,alphabet/finals/relation MAYEMPTY;DUPLICATE triples rejected in THIS model

Subset DFA ORIGINAL whole-word start:stage=0;seed set=[s19];previous set=[s19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, Yes], [1, s19, d19, Yes], [4, f19, e119, No], [5, e119, e219, No]];next set=[d19, m19, s19];stable=No

Subset DFA ORIGINAL whole-word start:stage=1;seed set=[s19];previous set=[d19, m19, s19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, Yes], [1, s19, d19, Yes], [4, f19, e119, No], [5, e119, e219, No]];next set=[d19, m19, s19];stable=Yes

Subset DFA ORIGINAL prefix step0:EXACT ORIGINAL supplied S=[d19, m19, s19];symbol=a19;ALL matching ORIGINAL edge rows=[[2, m19, m19]]

direct symbol targets=[m19];NO EPS preclosure inserted into S;now close ONLY these targets

Subset DFA ORIGINAL prefix step0 post-symbol EPS closure:stage=0;seed set=[m19];previous set=[m19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, No], [1, s19, d19, No], [4, f19, e119, No], [5, e119, e219, No]];next set=[m19];stable=Yes

Subset DFA ORIGINAL prefix step1:EXACT ORIGINAL supplied S=[m19];symbol=a19;ALL matching ORIGINAL edge rows=[[2, m19, m19]]

direct symbol targets=[m19];NO EPS preclosure inserted into S;now close ONLY these targets

Subset DFA ORIGINAL prefix step1 post-symbol EPS closure:stage=0;seed set=[m19];previous set=[m19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, No], [1, s19, d19, No], [4, f19, e119, No], [5, e119, e219, No]];next set=[m19];stable=Yes

Subset DFA ORIGINAL prefix step2:EXACT ORIGINAL supplied S=[m19];symbol=a19;ALL matching ORIGINAL edge rows=[[2, m19, m19]]

direct symbol targets=[m19];NO EPS preclosure inserted into S;now close ONLY these targets

Subset DFA ORIGINAL prefix step2 post-symbol EPS closure:stage=0;seed set=[m19];previous set=[m19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, No], [1, s19, d19, No], [4, f19, e119, No], [5, e119, e219, No]];next set=[m19];stable=Yes

Subset DFA ORIGINAL prefix step3:EXACT ORIGINAL supplied S=[m19];symbol=b19;ALL matching ORIGINAL edge rows=[[3, m19, f19]]

direct symbol targets=[f19];NO EPS preclosure inserted into S;now close ONLY these targets

Subset DFA ORIGINAL prefix step3 post-symbol EPS closure:stage=0;seed set=[f19];previous set=[f19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, No], [1, s19, d19, No], [4, f19, e119, Yes], [5, e119, e219, No]];next set=[e119, f19];stable=No

Subset DFA ORIGINAL prefix step3 post-symbol EPS closure:stage=1;seed set=[f19];previous set=[e119, f19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, No], [1, s19, d19, No], [4, f19, e119, Yes], [5, e119, e219, Yes]];next set=[e119, e219, f19];stable=No

Subset DFA ORIGINAL prefix step3 post-symbol EPS closure:stage=2;seed set=[f19];previous set=[e119, e219, f19]

ALL [ORIGINAL edge index,from,to,enabled] EPS rows=[[0, s19, m19, No], [1, s19, d19, No], [4, f19, e119, Yes], [5, e119, e219, Yes]];next set=[e119, e219, f19];stable=Yes

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=0;previous configs=[[s19, 0]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]]];next configs=[[s19, 0], [m19, 0], [d19, 0]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=1;previous configs=[[s19, 0], [m19, 0], [d19, 0]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=2;previous configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]], [[m19, 1], 2, [m19, 2]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=3;previous configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]], [[m19, 1], 2, [m19, 2]], [[m19, 2], 2, [m19, 3]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=4;previous configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]], [[m19, 1], 2, [m19, 2]], [[m19, 2], 2, [m19, 3]], [[m19, 3], 3, [f19, 4]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=5;previous configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]], [[m19, 1], 2, [m19, 2]], [[m19, 2], 2, [m19, 3]], [[m19, 3], 3, [f19, 4]], [[f19, 4], 4, [e119, 4]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4], [e119, 4]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=6;previous configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4], [e119, 4]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]], [[m19, 1], 2, [m19, 2]], [[m19, 2], 2, [m19, 3]], [[m19, 3], 3, [f19, 4]], [[f19, 4], 4, [e119, 4]], [[e119, 4], 5, [e219, 4]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4], [e119, 4], [e219, 4]];stable=No

ORIGINAL word=[a19, a19, a19, b19];direct NFA configuration stage=7;previous configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4], [e119, 4], [e219, 4]]

ALL enabled [from,ORIGINAL edge index,next] rows=[[[s19, 0], 0, [m19, 0]], [[s19, 0], 1, [d19, 0]], [[m19, 0], 2, [m19, 1]], [[m19, 1], 2, [m19, 2]], [[m19, 2], 2, [m19, 3]], [[m19, 3], 3, [f19, 4]], [[f19, 4], 4, [e119, 4]], [[e119, 4], 5, [e219, 4]]];next configs=[[s19, 0], [m19, 0], [d19, 0], [m19, 1], [m19, 2], [m19, 3], [f19, 4], [e119, 4], [e219, 4]];stable=Yes

ORIGINAL word=[a19, a19, a19, b19];ALL DFA prefix subsets=[[d19, m19, s19], [m19], [m19], [m19], [e119, e219, f19]];independent direct NFA prefix subsets=[[d19, m19, s19], [m19], [m19], [m19], [e119, e219, f19]]

prefix_invariant=Yes;accepted=Yes;base is EPS closure of start;for ANY prefix,append one symbol move then finite EPS suffix to obtain EXACTLY all next reachable states

Reverse checks

• S023 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S022 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S021 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S016 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S015 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S013 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S012 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S009 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S007 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S003 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.

Result

([a19, a19, a19, b19], [[d19, m19, s19], [m19], [m19], [m19], [e119, e219, f19]], [[d19, m19, s19], [m19], [m19], [m19], [e119, e219, f19]], Yes, Yes, each_DFA_prefix_subset_equals_all_epsilon_closed_NFA_states_reachable_after_that_prefix, No, finite_word_tests_do_not_prove_language_equivalence_without_the_prefix_induction_invariant)

The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.

This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.