可执行性问题

Question

是否可以有一个NFA决定实数？

Answer 1

没有。

一个实数的小数点后面可以有无限个数字。这些数字中可能没有系统（即，它们可能由随机过程生成）。在这种情况下，不可能描述比序列本身短得多的这个数字序列。

现在拿这样一个实数r。由于任何NFA只有状态的有限数量的，可以有限地描述，但是不足以接受仅实数[R（否则这将违背事实，不能有[R的有限描述）。

Answer 2

不，不能。非确定型有限自动机接受一串字符作为输入。所有字符串的集合都是可数的，因此小于实数集合。因此，甚至不能将任意实数编码为NFA的输入。