[問題] 證明是否是regular woody3724 PTT批踢踢實業坊

[問題] 證明是否是regular

作者: woody3724 (woody) 2013-11-15 00:08:00

題目:
Prove or disprove the following statement:
http://i.imgur.com/rnFeAKm.png
要證明是否是regular.
我的想法是分成3個case
3個case分別是 i = 0 i = 1 i = 2
用pumping lemma處理這三個case
但這樣用pumping lemma
似乎都得到它是regular
但這種題目不都通常要證它不是regular嗎
請高手解答
謝謝

作者: suhorng ( ) 2012-01-15 00:19:00

pumping lemma是說 regular => 必定....這題要證regular就直接給個RE或NFA或DFA

作者: woody3724 (woody) 2012-01-15 02:44:00

感謝　我畫出他的NFA了　

作者: isnoneval (虛物之海) 2012-01-15 12:08:00

處理 FA 我推薦 Myhill-Nerode Theorem, 太好用了直接檢驗充要條件, 檢驗完直接畫出 minimal DFA有了這個 pumping lemma for regex 可以整包丟掉了 XD

繼續閱讀

[問題]n位整數拿掉m數字得到最大數值PATRICKSTARS [問題] UVA 10578 - The Game of 31BombCat [問題] 演算法求時間複雜度woody3724 Re: [問題] 用induction證明無向圖必有一點為non-cutLeon Re: [問題] 用induction證明無向圖必有一點為non-cutDJWS Re: [問題] 用induction證明無向圖必有一點為non-cuteieio Re: [問題] 解題方法請教hioska [問題] 用induction證明無向圖必有一點為non-cutjvvbn0601 [問題] uva 200 WAArim [閒聊] What the fxxk ?j2se