[問題] 證明是否是regular

看板Prob_Solve作者 (woody)時間12年前 (2013/11/15 00:08), 編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 最新討論串1/2 (看更多)
題目: 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嗎 請高手解答 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.240.46
推
11/15 00:19, , 1F
pumping lemma是說 regular => 必定....
11/15 00:19, 1F
→
11/15 00:19, , 2F
這題要證regular就直接給個RE或NFA或DFA
11/15 00:19, 2F
→
11/15 02:44, , 3F
感謝　我畫出他的NFA了　
11/15 02:44, 3F
推
11/15 12:08, , 4F
處理 FA 我推薦 Myhill-Nerode Theorem, 太好用了
11/15 12:08, 4F
→
11/15 12:10, , 5F
直接檢驗充要條件, 檢驗完直接畫出 minimal DFA
11/15 12:10, 5F
→
11/15 12:10, , 6F
有了這個 pumping lemma for regex 可以整包丟掉了 XD
11/15 12:10, 6F
‣ 更多 woody3724 的文章
文章代碼(AID): #1IXFLY4d (Prob_Solve)
‣ 更多 woody3724 的文章
文章代碼(AID): #1IXFLY4d (Prob_Solve)