第 21508 題：上下文無關文法

原題與已知條件

finite disjoint nonterminals/terminals、start與complete production set。操作=cfg-bounded-search-boundary；資料={"nonterminals":["S7","A7"],"terminals":["a7","b7"],"start":"S7","productions":[["S7",["a7","A7"]],["A7",["b7","A7"]],["A7",[]]],"allow_epsilon":true,"word":["a7","b7","b7","b7"],"max_steps":2}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。

• G001 — finite disjoint nonterminals/terminals、start與complete production set。操作=cfg-bounded-search-boundary；資料={"nonterminals":["S7","A7"],"terminals":["a7","b7"],"start":"S7","productions":[["S7",["a7","A7"]],["A7",["b7","A7"]],["A7",[]]],"allow_epsilon":true,"word":["a7","b7","b7","b7"],"max_steps":2}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。

定義與適用範圍

沿用原題明示的論域、假設與來源 MKO 定義。本題已完成第二對話數理與中英語義覆核，並由原始參數逐題獨立重算模型、答案與每個算術步驟；原題仍為 candidate。

• mko-context-free-grammar

逐步推導

source operation=cfg-bounded-search-boundary;original snapshot and mathematics retained

explicit ordered source output fields=[word, max_steps, found_in_bounded_search, nonmembership_claim, boundary]

ORIGINAL production index=0;lhs=S7,rhs=[a7, A7];N=[S7, A7],T=[a7, b7],allow_epsilon=是

lhs is ONE declared nonterminal;every rhs symbol legal;empty rhs accepted ONLY under the explicit epsilon convention;original production position retained

ORIGINAL production index=1;lhs=A7,rhs=[b7, A7];N=[S7, A7],T=[a7, b7],allow_epsilon=是

lhs is ONE declared nonterminal;every rhs symbol legal;empty rhs accepted ONLY under the explicit epsilon convention;original production position retained

ORIGINAL production index=2;lhs=A7,rhs=[];N=[S7, A7],T=[a7, b7],allow_epsilon=是

lhs is ONE declared nonterminal;every rhs symbol legal;empty rhs accepted ONLY under the explicit epsilon convention;original production position retained

ORIGINAL unique disjoint N=[S7, A7],T=[a7, b7];start=S7;complete productions=[[S7, [a7, A7]], [A7, [b7, A7]], [A7, []]];allow_epsilon=是

start belongs to nonterminals;finite grammar qualified;NO derivation,membership,regularity,unambiguity or PDA equivalence inferred

ORIGINAL target form=[a7, b7, b7, b7];start=S7;max_steps=2;length cap=7

initial depth0 frontier=[[S7]];target already found=否;form equality itself does NOT require terminal-only target

ORIGINAL depth=0;ALL frontier forms=[[S7]];length cap=7

ALL [from,position,production_index,next,target_equal,within_cap] transitions=[[[S7], 0, 0, [a7, A7], 否, 是]];next distinct frontier=[[a7, A7]];any hit=否

ORIGINAL depth=1;ALL frontier forms=[[a7, A7]];length cap=7

ALL [from,position,production_index,next,target_equal,within_cap] transitions=[[[a7, A7], 1, 1, [a7, b7, A7], 否, 是], [[a7, A7], 1, 2, [a7], 否, 是]];next distinct frontier=[[a7], [a7, b7, A7]];any hit=否

ORIGINAL target=[a7, b7, b7, b7],depth bound=2;bounded found=否

nonmembership_claim fixed No whether found or not;longer or excluded derivations have NOT been ruled out

逐步反向核對

• S009 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S008 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S007 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S006 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S005 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S004 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S003 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S002 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
• S001 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。

結論

([a7, b7, b7, b7], 2, 否, 否, bounded_search_failure_cannot_prove_nonmembership_without_complete_bound)

依上列完整代值及條件核對得到原題答案；原題編號、格式與狀態保持不變。

本題覆核與來源綁定

覆核日期：2026-10-26

原題、答案、步驟表達式、數值 AST 與既有歷史保持原樣；原來的候選狀態屬於來源歷史，不覆寫為形式化證明。