[理工] 计理pumping lemma问题

楼主: usha9comeon (usha9comeon)   2017-11-26 23:22:51
大家好,
小妹最近在写计理遇到一个问题,
因为 pumping lemma 的假设是以DFA来做,
| w | >= M (DFA state 数量)
那如果这个假设改成“NFA“的话可以吗?
因为爬过很多文发现没有看到类似问题,
甚至看到有网站解释pumping lemma就是用NFA,
不过印象中以前上课是说不行的,
所以上来询问原因,
谢谢大家。
作者: alan23273850   2017-11-27 00:44:00
我以前上课是用DFA证明的,不妨列一下网站?
作者: FRAXIS (喔喔)   2017-11-27 19:48:00
应该是 DFA 和 NFA 都找不到..

Links booklink

Contact Us: admin [ a t ] ucptt.com