Вопрос о разрешимости

Question

Может ли быть NFA, который определяет реальные числа?

Answer 1

нет, не может. Недетерминированный конечный автомат принимает в качестве входных данных строку символов. Множество всех строк исчисляемо и, следовательно, меньше, чем множество действительных чисел. Поэтому вы даже не можете закодировать произвольное действительное число в качестве входных данных для NFA.

Answer 2

Нет.

Вещественное число может иметь бесконечное количество цифр после десятичной точки. В этих цифрах может отсутствовать система (то есть они могут генерироваться случайным процессом). В этом случае не может быть описания этой последовательности цифр, которое значительно короче самой последовательности.

Теперь возьмите такое действительное число r . Поскольку любой NFA имеет только конечное число состояний и может быть описан конечным образом, будет недостаточно принимать только действительное число r (иначе это противоречило бы тому факту, что быть конечным описанием r ).