The following diagram is an example of a deterministic finite state automaton , or DFA. This particular DFA describes an algorithm to determine if a sequence of characters is a properly formatted monetary amount with commas. For example, “$1,000” and “$25” and “$551,323,991,391” are properly formatted but “1,000” (no initial $) and “$1000” (missing comma) and “$5424,132” (missing comma) are not.

The DFA works by starting in the oval labeled IsMoney. This is the initial state. If the first character of the string is $, then we advance to the second character and move to state 0. Otherwise we conclude the string is not a proper monetary amount. In state 0, if the second character is a digit between 1 and 9, then we advance to the third character and move to state 1. Otherwise we conclude the string is not a proper monetary amount. In state 1, if we have no more characters left in the string, then we conclude that the string is a monetary amount. This is called a final state and is indicated by a bold oval. If the third character is a digit between 0 and 9, then we advance to the fourth character and move to state 2. Otherwise if the third character is a comma then we advance to the fourth character and move to state 4. Otherwise we conclude the string is not a proper monetary amount. The rest of the DFA behaves in a similar manner.

Write a program that uses recursion to implement the DFA. Your program should have a separate function for each state in the DFA. Each function should invoke the function corresponding to the next state indicated by the arrows in the diagram. There is mutual recursion because of the loop from state 7 to state 4. Test your solution with several strings and output whether each string is a properly formatted monetary amount.

This solution calls a function for every character in the string. However, the solution may be written in a tail-recursive manner, so it is possible that long strings will not exhaust the stack if your compiler is efficient.