Research Space for Linear Algebra & Discrete Mathematics
只要我們把字串uvw裡的u斷在第一個被重複走過的state就ok了, 畢竟如果原本取的uv會使得||uv||>N, 那根據鴿籠就表示裡面一定還有重複的部分, 所以一定還可以取到更短的uv, 這個結果通常會視為是pumping lemma的一部分這樣後面的||w||≧2你應該就知道為什麼了; 這裡主要是因為 p 取的夠大所以可以保證 w 不會是空字串
助教大大說"字串uvw裡的u斷在第一個被重複走過的state"但是如果uv的長度不大於N~怎麼確保字串uv中會有重複走過的state呢??
感謝助教~~我有部分懂了,還剩一點小問題,我po照片問,比較好讓助教了解我的想法
或許你再重新把這整個程序想過一遍會更加清楚: 一開始我們是先取了一個α使得||α||>=N, 之後才由pumping lemma裡鴿籠原理的想法來確保會有重複走過的state, 此時才決定uvw要斷在哪裡的, 然後在斷了之後才得到||uv||<=N這樣的結果 (原因就是像我之前打的, 去找第一個重複的), 並不是先有||uv||<=N的條件才來看裡面的state會不會重複, 所以對於由原本的α所決定的uv, 不管uv長度是多少, 這當中一定會有重複的state
瞭解了~順序是 1: uvw 長度>N+1 2:造成迴圈v 3:確認了V在哪 4:所以uv長度小於等於N+1謝謝強者助教^^那課本上p取大於N+1是不是也可以取等號??( N+1也可能是質數)
取 p=N+1 照原本的證明路線走會推不出矛盾:若取 p>=N+1, 因為 ||uv||<=N=> ||w||>=1=> ||uw||>=1, 取 i=||uw||,則 ||u(v^i)w|| = ... = (1+||v||)||uw||推到這裡就會發現這還是有可能會是質數,畢竟雖然(1+||v||)>=2, 但||uw||有可能是1
謝謝助教詳盡的解說,一一的把我錯誤觀念導通~我全懂了 ^^
張貼留言
7 則留言:
只要我們把字串uvw裡的u斷在第一個被重複走過的state就ok了, 畢竟如果原本取的uv會使得||uv||>N, 那根據鴿籠就表示裡面一定還有重複的部分, 所以一定還可以取到更短的uv, 這個結果通常會視為是pumping lemma的一部分
這樣後面的||w||≧2你應該就知道為什麼了; 這裡主要是因為 p 取的夠大所以可以保證 w 不會是空字串
助教大大說
"字串uvw裡的u斷在第一個被重複走過的state"
但是如果uv的長度不大於N~怎麼確保字串uv中會有重複走過的state呢??
感謝助教~~我有部分懂了,還剩一點小問題,我po照片問,比較好讓助教了解我的想法
或許你再重新把這整個程序想過一遍會更加清楚: 一開始我們是先取了一個α使得||α||>=N, 之後才由pumping lemma裡鴿籠原理的想法來確保會有重複走過的state, 此時才決定uvw要斷在哪裡的, 然後在斷了之後才得到||uv||<=N這樣的結果 (原因就是像我之前打的, 去找第一個重複的), 並不是先有||uv||<=N的條件才來看裡面的state會不會重複, 所以對於由原本的α所決定的uv, 不管uv長度是多少, 這當中一定會有重複的state
瞭解了~順序是 1: uvw 長度>N+1
2:造成迴圈v
3:確認了V在哪
4:所以uv長度小於等於N+1
謝謝強者助教^^
那課本上p取大於N+1
是不是也可以取等號??( N+1也可能是質數)
取 p=N+1 照原本的證明路線走會推不出矛盾:
若取 p>=N+1, 因為 ||uv||<=N
=> ||w||>=1
=> ||uw||>=1, 取 i=||uw||,
則 ||u(v^i)w|| = ... = (1+||v||)||uw||
推到這裡就會發現這還是有可能會是質數,
畢竟雖然(1+||v||)>=2, 但||uw||有可能是1
謝謝助教詳盡的解說,一一的把我錯誤觀念導通~我全懂了 ^^
張貼留言