12. The following diagram is an example of a deterministic finite state automaton, or DFA. This...

 

Transcribed Image Text:

12. 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. IsMoney 1-9 0-9 0-9 State 0 State 1 State 2 State 3 0-9 0-9 0-9 State 4 State 5 State 6 State 7 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 ad- vance to the third character and move to state 1. Ötherwise 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 dia- gram. 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 solu- tion 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. 12. 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. IsMoney 1-9 0-9 0-9 State 0 State 1 State 2 State 3 0-9 0-9 0-9 State 4 State 5 State 6 State 7 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 ad- vance to the third character and move to state 1. Ötherwise 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 dia- gram. 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 solu- tion 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.

Answer rating: 100% (QA)

1 invalid amount 2a valid amount inlude using stdut usin... View the full answer