Design a FSA that will recognize sentences such as “There’s aflea on the speck on the frog on the bump on the branch on the login the hole in the bottom of the sea.” Namely, the sentences shouldlook like “There’s an THING1 on/in the THING2 on/in the THING3 …on/in the THINGn”, where THINGn is a thing, and where the maximum ncan be arbitrarily large. Assume that words are fed to the FSA oneat a time (not a character at a time), and your FSA may include onespecial transition that tests whether a word represents a noun ornot.