推 ddczx:若L為有限狀態語言,則存在有限狀態機M認知L,設其有n個狀態 09/23 00:29
→ ddczx:考慮字串d=a^n*b^n,設此字串輸入到被接受的狀態變化為: 09/23 00:30
→ ddczx:S0->S1->....->Sn->.....->S2n,則S0~Sn有n+1個狀態, 09/23 00:30
→ ddczx:故存在Si=Sj,i=/=j 09/23 00:32
→ ddczx:代表存在一更短路徑字串a^m*b^n,m<n而被接受, 09/23 00:32
→ ddczx:與L={a^k*b^k |k>=1}不合 09/23 00:32
→ bouwhat:懂了！感謝d大！ 09/23 12:45