可執行性問題

Question

是否可以有一個NFA決定實數？

Answer 1

沒有。

一個實數的小數點後面可以有無限個數字。這些數字中可能沒有系統（即，它們可能由隨機過程生成）。在這種情況下，不可能描述比序列本身短得多的這個數字序列。

現在拿這樣一個實數r。由於任何NFA只有狀態的有限數量的，可以有限地描述，但是不足以接受僅實數[R（否則這將違背事實，不能有[R的有限描述）。

Answer 2

不，不能。非確定型有限自動機接受一串字符作爲輸入。所有字符串的集合都是可數的，因此小於實數集合。因此，甚至不能將任意實數編碼爲NFA的輸入。