Can there be an NFA that decides on real numbers ?
+4
A:
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).
Stephan202
2009-12-06 15:02:02
+5
A:
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.
Josef Grahn
2009-12-06 15:02:19
A:
I am somewhat confused by the answers here. If we forget the real numbers for a second and just concentrate on the fractions (represented as decimal expansions), can we decide on 1/3? This input has infinite length and you can't know it's 1/3 until you finish. (It might have a 4 in some far off decimal place - although this number should also be accepted if 1/3 is accepted.)
An NFA must have a finite alphabet (in this case 0-9 and '.'). It also has a start state (no problem). It has a FINITE set of states and a FINITE set of accept states (which is a subset of the total states.)
Now it seems that the NFA won't halt for any infinitely repeating decimal (like 1/3). So it would seem that the decidability of the reals would be the same as the decidability of the rationals. I don't think that you need to point to uncountable reals in order to solve this.
Is my reasoning correct?
No One in Particular
2009-12-06 15:39:10
Ask yourself this question: how does a finite automaton (FA) accept infinite strings anyway? The answer is that an FA accepts an infinite string *s* if the the set of states that are infinitely often visited according to *s* contains at least one accepting state. See e.g. www.tcs.tifr.res.in/~pandya/grad/aut06/lect4.pdf. So it's is not hard to create an automaton that accepts 1/3: just create a single accepting state that has a reflexive transition labelled with *3*.
Stephan202
2009-12-06 15:50:35
To answer your question, the reason an FSM can't decide any language involving all reals is that it's impossible to come up with a finite representation for reals. Since rationals are countable, you can come up with a finite representation for all rationals (e.g. reduced numerator/denominator pairs; quote notation). This is necessary but not sufficient for decidability. There are proper supersets of rationals that are countable and non-decidable, such as (I believe) definable numbers.
outis
2009-12-06 16:15:03
So outis, are you saying that we can decide the rationals because we can put them in fraction form (instead of decimal form) and then construct a FSM for [0-9]* '/' [0-9]* ? How would you construct a FSM for an INFINITE string which would halt? The machine would not halt (since the input is infinite), but I can see how you could construct a FSM which would recognize 1/3 in the abstract. (Just have 3->3 transition to the same state and have that be an accept state. I can look at this and know that for 1/3 it goes to state '3' and stays there.)
No One in Particular
2009-12-07 02:35:18
outis
2009-12-08 23:53:22
Finite input representation is a necessary but not sufficient requirement for FSAs. For automata that can handle infinite input (called Büchi automata or ω automata), see http://en.wikipedia.org/wiki/B%C3%BCchi_automaton and the doc Stephan202 links to.
outis
2009-12-09 00:06:24