創作內容

1 GP

正規語言學徒:Pumping lemma 泵引理

作者:Absinthe│2020-05-05 00:13:55│巴幣:2│人氣:717
一句話解釋泵引理如何找矛盾:調整y重複的次數,選擇泵入或泵出,使得w變得不屬於RL發生矛盾,證明原本suppose L=RL是錯的,我們必須接受L不是Regular。


白話文解釋證明步驟:
先找一個字串w其長度需大於等於L的狀態數N,
同時此字串w的內容要精心設計,必須將w字串的子字串xy的長度鎖在N之中,最好是讓xy鎖在相同的字符裡,這樣才方便讓y重複k次,導致矛盾產生(通常題目的L: 字符ab的長度有相關,設法讓y重複k次,使得ab長度關係被打破)
最後調整y重複的次數,選擇泵入或泵出,使得w變得不屬於RL,發生矛盾,證明原本suppose L=RL是錯的,我們必須接受L不是Regular。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4771679
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

1喜歡★Absinthe1010 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:真的覺得自己太嫩了... 後一篇:我發現自己看英文都會心中...

追蹤私訊切換新版閱覽

作品資料夾

happy545午安阿~~
準備以後的規劃,不然寫作進步太慢了...看更多我要大聲說昨天16:19


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】