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