[问题] 证明是否是regular woody3724 PTT批踢踢实业坊

[问题] 证明是否是regular

楼主: woody3724 (woody) 2013-11-15 00:08:00

题目:
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吗
请高手解答
谢谢

作者: suhorng ( ) 2012-01-15 00:19:00

pumping lemma是说 regular => 必定....这题要证regular就直接给个RE或NFA或DFA

楼主: woody3724 (woody) 2012-01-15 02:44:00

感谢　我画出他的NFA了　

作者: isnoneval (虚物之海) 2012-01-15 12:08:00

处理 FA 我推荐 Myhill-Nerode Theorem, 太好用了直接检验充要条件, 检验完直接画出 minimal DFA有了这个 pumping lemma for regex 可以整包丢掉了 XD

继续阅读

[问题]n位整数拿掉m数字得到最大数值PATRICKSTARS [问题] UVA 10578 - The Game of 31BombCat [问题] 算法求时间复杂度woody3724 Re: [问题] 用induction证明无向图必有一点为non-cutLeon Re: [问题] 用induction证明无向图必有一点为non-cutDJWS Re: [问题] 用induction证明无向图必有一点为non-cuteieio Re: [问题] 解题方法请教hioska [问题] 用induction证明无向图必有一点为non-cutjvvbn0601 [问题] uva 200 WAArim [闲聊] What the fxxk ?j2se