※ 引述《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」這句話而已