PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 證明是否是regular

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (f0VMRgEBA)時間11年前 (2013/11/15 00:33)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串2/2 (看更多)

※ 引述《woody3724 (woody)》之銘言： : 題目: : 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嗎 : 請高手解答 : 謝謝你再仔細看一下題目它的條件是 j > (i mod 3) 也就是 i 跟 j 可能可以很大但 j 至少比 i 除以 3 的餘數大例如 i = 11, j = 1 就不行了 (11 mod 3 = 2) 然後這個 language 確實是 regular ┌─────┐ 一個 decide 它的 DFA 如左 (走不動 = reject) ↓ │0 →○─→○─→○ 上面三個狀態是在計算 i mod 3 │ 0 │ 0 │ │1 │1 │1 由左至右分別是 0, 1, 2 1 ↓ ↓ ↓ ┌◎←─○←─○ 然後再分別看到超過那麼多的 1 才到達 Accept state ◎ │↑ 1 1 └┘ 於是這個 DFA 確實 decide 這 language 或者我們也可以寫出它的對應 regular expression: ((000)*11*)|(0(000)*111*)|(00(000)*1111*) 就是直譯「分別在 i 餘 0 餘 1 餘 2 三種狀況, 後面要超過餘數數量的 1」這句話而已 -- 嘛, 雖然這種題目一開始先試反證無可厚非但當似乎無法反證時就要考慮是不是其實它是對的了這題正好就是這種狀況 -- 1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町つぐみ歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬チサト 1998/06/18 守野くるみ打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙 2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.41.34.213