0
Peut-il y avoir un NFA qui décide des nombres réels?Une question de décidabilité
A
Répondre
5
Non.
Un nombre réel peut avoir un nombre infini de chiffres derrière la virgule décimale. Il peut ne pas y avoir de système dans ces chiffres (c'est-à-dire qu'ils peuvent être générés par un processus aléatoire). Dans ce cas, il ne peut pas y avoir de description de cette séquence de chiffres significativement plus courte que la séquence elle-même.
Prenez maintenant un tel nombre réel r. Puisque tout NFA a seulement un nombre fini d'états et peut être décrit finiment, il sera inadéquat d'accepter seulement le vrai nombre r (pour le contraire cela contredirait le fait qu'il ne peut pas y avoir une description finie de r).
6
Non, il ne peut pas. Un automate fini non déterministe accepte une chaîne de caractères en entrée. L'ensemble de toutes les chaînes est dénombrable, et donc plus petit que l'ensemble des nombres réels. Par conséquent, vous ne pouvez même pas encoder un nombre réel arbitraire en tant qu'entrée dans le NFA.
Pouvez-vous clarifier s'il vous plaît? Décide quoi sur les nombres réels? Accepte les nombres réels et rejette les nombres complexes? – Dima
Quel est le but de cette question? Devoirs? Curiosité? – outis