Mar*_*ere 0 turing-machines nfa pushdown-automaton
可以有一个决定实数的NFA吗？
Jos*_*ahn 6
不,不可能.非确定性有限自动机接受一串字符作为输入.所有字符串的集合都是可数的,因此小于实数集合.因此,您甚至无法将任意实数编码为NFA的输入.
Ste*_*202 5
不.
实数可以在小数点后面具有无限数量的数字.这些数字中可能没有系统(即,它们可能由随机过程生成).在这种情况下,不能对这个数字序列的描述明显比序列本身短.
现在拿一个真正的数字r.由于任何NFA只有有限数量的状态并且可以有限地描述,因此仅接受实数r是不够的(否则将与r不能有限描述的事实相矛盾).
归档时间：
15 年，9 月 前
查看次数：
221 次
最近记录：