Re: [問題] 證明是否是regular
※ 引述《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
→
11/15 02:45, , 1F
11/15 02:45, 1F
推
11/15 11:51, , 2F
11/15 11:51, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：