derivation-mko-pumping-lemma-regular-languages-01 · ocme-new142-reader-adoption-20261021
可見量詞次序、全pump count迴圈證明及全部合法splits。
regular必要條件，非充分條件；不以有限pump tests證regular。
workG1 — 前半令D為任意完整DFA，R=L(D)，p=|Q|≥1。後半的L={a^n b^n:n≥0}是另一本欲否定regular的語言；其p只在前半必要條件證成後由regular假設取得。p — DFA state數或假設pumping長度r,s — 全部split參數i — 最後選的pump countmko_definition · cited — 固定量詞順序exists p forall w in L with |w|≥p exists x,y,z forall i≥0，且w=xyz、|xy|≤p、|y|>0、xy^i z∈L。regular positive family由完整DFA run中的repeated-state loop提供對所有i的symbolic closure，不只測若干i。對L={a^n b^n}選w=a^p b^p，完整枚舉所有合法splits；每個y皆只含a，選i=0即離開L。單一decomposition、有限words或bounded checks不能證regular，且不得倒置對手選word與證明者選decomposition的量詞。 · mko-pumping-lemma-regular-languageswork · prerequisite — regular語言可由完整有限DFA接受；另使用DFA確定run、鴿籠原理、word分割與長度、數學歸納和量詞否定。目標宣告只是設定待證命題；pumping必要性由DFA run證成，不作自身前提。操作前
\mathcal T:\ R\text{ regular}\Longrightarrow\text{the following pumping condition}操作後
\text{Target: }\exists p\ge1\ \forall w\in R,\ |w|\ge p\ \exists x,y,z\ \forall i\ge0:\ w=xyz,\ |xy|\le p,\ |y|>0,\ xy^iz\in R條件：無
規則：work · 依賴：G1, work
葉節點依據：work
此步只設定待證目標與量詞責任，不宣告目標已成立：word先選，split後選，pump count最後選。
操作前
w\in R,\ |w|\ge p\text{ arbitrary};\quad q_j=\delta^*(q_0,w[0:j])\ (0\le j\le p)操作後
\exists0\le r<s\le p:\ q_r=q_s
條件：無
規則：work · 依賴：G1, work
葉節點依據：work
任取合格word，前p個symbol給p+1個prefix位置落p個states，鴿籠給重複state。
操作前
x=w[0:r],\ y=w[r:s],\ z=w[s:|w|]
操作後
|xy|=s\le p,\quad|y|=s-r>0,\quad\delta^*(q_r,y)=q_r
條件：無
規則：work · 依賴：G1, S02, work
葉節點依據：work
重複state間word片段形成非空loop。
操作前
\delta^*(q_r,y)=q_r,\quad\delta^*(q_0,w)\in F
操作後
\forall i\ge0:\ \delta^*(q_0,xy^iz)=\delta^*(q_0,w)\in F
條件：無
規則：work · 依賴：G1, S03, work
葉節點依據：work
i=0空loop是base，每多一次y回同state；歸納證所有pump counts均接受。w原先任意，故此刻才完成S01全稱目標。
操作前
\text{assume }L=\{a^nb^n:n\ge0\}\text{ regular};\quad p\text{ from the proved condition}操作後
w=a^pb^p\in L,\quad |w|=2p\ge p
條件：無
規則：work · 依賴：G1, S04, work
葉節點依據：work
regular語言具有完整DFA，故現在可用S04已證的必要條件取得p，再選反證word。
操作前
w=xyz,\quad|xy|\le p,\quad|y|>0
操作後
x=a^r,\quad y=a^s,\quad z=a^{p-r-s}b^p,\quad0\le r,\ 1\le s,\ r+s\le p條件：無
規則：work · 依賴：G1, S05, work
葉節點依據：work
任意合法split都完全落前p個a內；以(r,s)參數列出全部splits。
操作前
\forall(r,s):0\le r,\ 1\le s,\ r+s\le p,\quad i=0
操作後
xy^0z=a^{p-s}b^p\notin L\quad\text{since }p-s<p條件：無
規則：work · 依賴：G1, S06, work
葉節點依據：work
對每個合法split，同一pump count0都破壞a與b數相等。
操作前
\forall p\ge1\ \exists w\in L\ \forall\text{ legal splits}\ \exists i\ge0:\ xy^iz\notin L操作後
L=\{a^nb^n:n\ge0\}\text{ is not regular}條件：無
規則：work · 依賴：G1, S07, work
葉節點依據：work
這是pumping必要條件的量詞否定，因此反證regular假設。
本稿無局部子步。
S08 · premise_audit · G1, S07, work — 對照p=3時全部(r,s)為(0,1),(0,2),(0,3),(1,1),(1,2),(2,1)，皆由同公式拒絕。S07 · premise_audit · G1, S06, work — s≥1保證嚴格少a，涵蓋全部splits而非選一案。S06 · premise_audit · G1, S05, work — 沒有假定prover選某個特定split。S05 · premise_audit · G1, S04, work — p先由regular假設及已證條件給出，word再依p選；不是把欲證目標當原始given。S04 · premise_audit · G1, S03, work — 結論來自loop invariant，不是測幾個i；|Q|給對所有合格w共同的p。S03 · premise_audit · G1, S02, work — half-open slices給xyz=w且不漏字元。S02 · premise_audit · G1, work — states序列包含讀零個symbol的q0；論證只用DFA與鴿籠，不用未證目標。S01 · premise_audit · G1, work — 目標將由S02至S04證明；不可把目標自身用作那些證明的前提。p先給、word再選、split回應、i最後攻擊。
以0≤r、1≤s、r+s≤p完整參數化，不列幾個samples代替。
reject — 須對prover所有合法splits都提供失敗i。reject — 必要條件不等充分條件，且要求全words、全i。reject — |xy|≤p而前p字元全a，故y只含a。DFA loop證regular語言的必要pumping property；全部合法splits使a^n b^n非regular。
3 個本稿宣告算術檢查；只支持所列算式。
b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f74020259b19fb881bf3f9e3f2ce15d36f3ba93deaa04bee651ffdee1cc305948ba5e44306bc5a91679067d83527f25fce70d5e9a74dad386eb916092392fbdb2SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW