CS337 Project 3Finite State MachinesTA: Yan Li ([email protected])Release Date: Oct. 27, 2008 (Monday)Due Date: Nov. 10, 2008 11:59 PM (Monday)1 OverviewIn this project, you and your partner (please find a partner early!) will create some simpleFinite State Machines(FSMs), then implement a finite state machine interpreter to test yourFSMs o n input strings. This project consists of three parts:part 1: Create seven finite state machines to match the given string patterns. You do notneed to turnin anything for this part but they will be used for part 2.part 2: Translate the diagram of each FSM from part 1 into a format (saved into a filefor each FSM) that can be read by a computer program.part 3: Implement a program that reads any description files of FSMs (obtained frompart 2 or any other .fsm files in the same format) and a file of strings, and prints if yourfinite state machines accepts the input strings.The alphabet fo r this project is (Note: no uppercase letter in this alphabet and space isnot part of the alphabet.):abcdefghijklmnopqrstuvwxyz0123456789~!@#%^&*()-+{}.,There are four uppercase letters we will use as shorthand for different sets of the alphabetwhich you should use in your FSM description files in part 2. And you MUST implementthese shortcuts in part 3.(‘A’) Alphabetic: abcdefghijklmnopqrstuvwxyz(‘D’) Digit: 0123456789(‘N’) Non-Zero: 123456789(‘S’) Symbolic: ~!@#%^&*()-+{}.,12 Part 1Use the notatio n described in class to create a unique finite state diagram for each of thefollowing seven string descriptions. Number the state in each FSM as 1, 2, 3, .... So thestart state for each machine should be 1. Refer to Figure 1 for an example of a finite statediagram. You do not need to turn in anything for this part. But these diagrams will be usedin Part 2.NOTE: You do not need to make reject state in the FSMs. Draw the transitions only forvalid inputs and any other input not shown would be considered as going to the reject state.Warning: The empty string must be rejected by all Finite State Machines.1. Accept only integers, where integers are defined as either a single 0, or a nonzero digitfollowed by any number of digits. Examples: 0, 3802 will be accepted. But 061 shouldbe rejected.2. Accept only comma-separated integers (use integer as defined above). Examples: 2, 000or 6, 500, 000 will be accepted. But 3000 and 3, 00, 0 must be rejected. Note that thecommas must be in the thousandth, millionth, billionth, etc. po sitions. If the numberis 999 or less it should be accepted.3. Accept signed and unsigned integers (use integer as defined above). Examples: −5,+45, 45, and 0 will be accepted. But +0, −45.5, and −0.3 must be rejected.4. Accept any string that uses the defined a lphabet if it contains a keyword “begin” and/or“end”. Examples “erikbegin”, “xendd” and “ebeginend” will be accepted. But “began”must be rejected.5. Accept unsigned floating point numbers which MUST contain one decimal point in thenumber. With floating point numbers, a 0 can be the leading digit but only if it is theonly digit before the decimal. Examples: 0.003, 0.20 , 0.000, 3.54 will be accepted. But0..03, 1., 55, and 01.33 must be rejected.6. Accept a string with up to 3 levels of balanced par entheses, ignoring the charactersbetween, before, or after the parentheses. Reject the string if the parentheses areunbalanced, if there are no parentheses in the string, or if the nesting is deeper thanthree. Examples: “compute((1+2)+((5+2*8+2) ) )”, and “((()))” will be accepted. But“((((4))))”, “(() () ) )”, and “4+3” will be rejected.7. Accept a string of digits if they are non-increasing. Examples: 5443, 4, 22 and 6 31 willbe accepted. But 234 must be rejected.3 Part 2In this part, you will convert each of the finite state machine diagrams from part 1 into atext file (.fsm) that can be r ead by a computer program. The 7 .fsm files must be called“machine1.fsm”, . . . , “machine7.fsm”. The .fsm file format to describe a FSM is as follows.21 20 011StartFigure 1: An FSM that accepts strings with an odd number of 1s.Each line in the file represents a single state in the FSM diagram. Below is the file calledmachine0.fsm which is the machine-readable form of the diagram in Figure 1:1 1:0 2:12 1:1 2:0 XEach line has the fo llowing format:[State Name] [NextState Name]:[Transitions] [Accepting State?]The first token in each line is the state name. For your implementatio n you can expectto see only unsigned numbers for state names. In the above example, the first line describesstate 1, the second line describes state 2. The state number will not exceed exceed a Javaint.The Finite State Machine Interpreter will always look for, and start with, the state la beled1. The states do not have to be in order, and there can be gaps in the numbering. A statecan only be listed once per file.After each state name, there can be an arbitrary number of additional tokens. There aretwo types of tokens, Accepting State Flags, and Next Step Pairs.An Accepting State Flag (ASF) is the capital letter ‘X’. When an ASF is on the line, itmeans the current state is an accepting state.Note: The flag can appear before, after, or anywhere in between ot her Next Step Pairtokens.In the example file, state 2 has an ASF, so if the input string terminates in state 2, thestring is accepted. State 1 does not have an ASF, so if t he string ends there, it will berejected.A Next Step Pair consists o f the next state name, followed by a colon (“:”) and thenthe valid characters that allow the transition from current state to next state to take place.There must not be any spaces between the name, colon, and transition characters. In theexample, state 1 transitions back to state 1 if a ‘0’ is encountered–a loop. State 1 transitionsto state 2 if a ‘1’ is encountered.If [Transitions] has more than one symbol then you should write all the symbo ls togetherwithout any space. For example, in a FSM M, if state 5 transitions to state 1 when the inputcharacter is either ‘a’ or ‘b’; and state 5 transitions to state 2 if a ‘0’ or ‘1’ is encountered,then the line in the corresponding M.fsm file will be as follows:35 1:ab 2:01Remember the shorthand mentioned in Part 1: If the next character in the string is notmentioned in the current state, then the string is immediately rejected (i.e., you should notmake a reject state).You should use the four uppercase