※ 引述《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