※ 引述《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”这句话而已