Research Space for Linear Algebra & Discrete Mathematics
這裡會得證是因為 (a^(N-x))(b^N), x≧1 會被 M 所接受, 這矛盾了 M 應該要認知 L={(a^k)(b^k)|k≧1}, 而pumping lemma有點像是把這裡利用鴿籠原理來證明裡的想法做一個推廣如果要以pumping lemma的寫法來說明矛盾, 一種寫法是: 假設 (a^k)(b^k)=uvw, 其中 u(v^i)w∈L, for all i≧0, 如果v只是由含有數個a所組成的非空字串, 則取 uvvw∈L 為一具有a比b還要多的字串, 這矛盾了L的定義; 如果v只含有數個b, 則矛盾的理由同上; 如果v裡同時具有a又有b, 則uvvw會使得a,b交錯出現, 同理也矛盾了L的定義
助教我有個疑問 假如要我設計FSA矛盾FSL的話 是我要取一個 u(v^i)w∈L 矛盾某件事情不成立 還是要矛盾不管我輸入任何字串都不成立？？？因為只要矛盾某件FSL不成立的話我的FSA可以設計很多種 例如 97北科{A︿P |P為質數}的那題
因為pumping lemma是說要 u(v^i)w∈L, for all i≧0, 所以只要找到一個 i≧0 使得 u(v^i)w∉L 就足以矛盾已知了, 不用證到 for all
張貼留言
3 則留言:
這裡會得證是因為 (a^(N-x))(b^N), x≧1 會被 M 所接受, 這矛盾了 M 應該要認知 L={(a^k)(b^k)|k≧1}, 而pumping lemma有點像是把這裡利用鴿籠原理來證明裡的想法做一個推廣
如果要以pumping lemma的寫法來說明矛盾, 一種寫法是: 假設 (a^k)(b^k)=uvw, 其中 u(v^i)w∈L, for all i≧0, 如果v只是由含有數個a所組成的非空字串, 則取 uvvw∈L 為一具有a比b還要多的字串, 這矛盾了L的定義; 如果v只含有數個b, 則矛盾的理由同上; 如果v裡同時具有a又有b, 則uvvw會使得a,b交錯出現, 同理也矛盾了L的定義
助教我有個疑問 假如要我設計FSA矛盾FSL的話 是我要取一個 u(v^i)w∈L 矛盾某件事情不成立 還是要矛盾不管我輸入任何字串都不成立？？？因為只要矛盾某件FSL不成立的話我的FSA可以設計很多種 例如 97北科{A︿P |P為質數}的那題
因為pumping lemma是說要 u(v^i)w∈L, for all i≧0, 所以只要找到一個 i≧0 使得 u(v^i)w∉L 就足以矛盾已知了, 不用證到 for all
張貼留言