Design Finite Automata & Program Finite Automata Simulator

Task: Suppose you want to use pattern matching to identify email messages that are spam email given a collection of emails. Specifications: Design and implement an FA that accepts strings such as “free access”, “free software”, “free vacation”, “free trials”, and “win/winner(s)”. These strings must be in the body of the message not the subject. Thus, the language to be accepted by your automaton is as follows. L = { w = “free access”, w = “free software”, w = “free vacation”, w = “free trials”, w = “win”, w = “winner”, w = “winners”, w = “winnings”} The body of the message may or may not have these strings within “ “. Your automaton must accept these strings within “ “ and without “ “. The implementation of the FA must simulate the FA by reading an input symbol, computing the transition function and displaying the state or set of states the FA reaches when processing this symbol. Your FA must process one symbol at a time, not words or phrases at a time. Input: A text file named [login to view URL] with xml tags as shown below. Each message is a document identified by msgN, where N is a number starting with 1. <DOC> <DOCID> msgN </DOCID> Subject ... body of the email ... </DOC> The entire text of the email is normalized; that is, all characters are lower case, and there is a space in between words and punctuation. Output: Display each state reached when your FA process one input symbol. When your program finishes processing all the emails display the emails’ IDs of those messages identified as spam. Guidelines 1. The project must be in C++. 2. Prepare a README file. 3. An input file named [login to view URL] is attached for you to test your program. Hope you have fun!