Scanning Numbers
Looking for fixed point numbers
Consider the problem of trying to determine whether a string of characters is a fixed point number, that is, a number with a decimal point, like 24.0 or 57.94, or 0.87. This is a problem that compilers have to deal with.
We can design a finite state automaton to check any string of digits and decimal points to see if they match the desired pattern or not. For example, the automaton should accept strings like 34.5 or 3.14159, but not strings like 35, or 35.89.5.
In order to get started, we need a clear definition of what constitutes a proper fixed point number. Let's say it is this:
A fixed point number is any string of characters that starts with one or more other digits, which are followed by a decimal point, which are followed by one or more digits.
A first attempt
A first attempt at constructing a finite state automaton might look like the following.
The first state, which is also the starting state, accepts any number of digits. If a decimal point is found, a second state is reached which again accepts any number of digits. The first state remembers that digits have been seen. The second state, which is also the accept state, remembers that some digits followed by a decimal point followed by some more digits have been seen.
Does this automaton do the trick? Try it with numbers like 45.9, or 3.14159. It correctly accepts those strings as correct. It also will not accept strings like 35.89.5, or 35 (with no decimal point).
However, there is a subtle problem with this finite state automaton which a novice might not recognize right away. Try running the automaton with .5 and then with 5., and then with just . (the decimal point). The automaton accepts these strings, which it should not.
What is the problem. The problem is that we haven't designed our automaton to ensure that there is always at least one digit before and one digit after the decimal point. This problem represents a common mistake that beginners make when designing finite state automata. They construct an automaton that accepts all correct strings, but which also accepts some incorrect ones. That is, they forget to ensure that all improperly formed strings are rejected. On the next page we rectify this problem.
