作者woody3724 (woody)
站内Prob_Solve
标题[问题] 证明是否是regular
时间Fri Nov 15 00:08:00 2013
题目:
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吗
请高手解答
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.240.46
1F：推 suhorng:pumping lemma是说 regular => 必定.... 11/15 00:19
2F：→ suhorng:这题要证regular就直接给个RE或NFA或DFA 11/15 00:19
3F：→ woody3724:感谢 我画出他的NFA了 11/15 02:44
4F：推 isnoneval:处理 FA 我推荐 Myhill-Nerode Theorem, 太好用了 11/15 12:08
5F：→ isnoneval:直接检验充要条件, 检验完直接画出 minimal DFA 11/15 12:10
6F：→ isnoneval:有了这个 pumping lemma for regex 可以整包丢掉了 XD 11/15 12:10