小屋創作

日誌2020-05-05 00:13

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

作者:Absinthe

一句話解釋泵引理如何找矛盾:調整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。

1

0

LINE 分享

相關創作

【市集小吃】2024/04/28拜日、土城大潤發餐車市集

近況-015

【yotoo】240430

留言

開啟 APP

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

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