A Decidability Question

Can there be an NFA开发者_StackOverflow that decides on real numbers ?

No, there can not. A nondeterministic finite automaton accepts a string of characters as input. The set of all strings is countable, and hence smaller than the set of real numbers. Therefore, you cannot even encode an arbitrary real number as input to the NFA.

Nope.

A real number can have an infinite number of digits behind the decimal point. There may not be a system in those digits (i.e., they may be generated by a random process). In that case there cannot be a description of this sequence of digits that is significantly shorter than the sequence itself.

Now take such a real number r. Since any NFA has only a finite number of states and can be described finitely, it will be inadequate to accept only the real number r (for otherwise that would contradict the fact that there cannot be a finite description of r).