Problem $1$: FSA $(30$ pts$)$

Design an FSA that checks if a given email address is in the correct format $[1],$ as follows:

An email address is divided into two parts: local part, followed by the $$@$$ symbol, followed by the domain part. The local part consists of any combination of alphabetic characters, digits, or any of the following special characters:

$!$ # $ $\%$ &$*+/=?^\_`.\{|\}$ ~

The only other constraint for the local part is that the period character cannot be the first or last character, and there cannot be two or more consecutive periods. The domain part should be a series of period$-$separated DNS labels. $($Example: cs$.$fiu.edu$)$ Each DNS label consist of any combination of alphabetic characters, digits, and hyphens. The labels cannot be all numeric and hyphens cannot be the first or last character of a label.

$[1]$ Email address format as defined by RFC $3696,5321,5322,6530.$

Problem $2$: Regular Expressions $(10$ pts$)$

Write your solution to Problem $1$ as a regular expression, using the conventions as described in the textbook.

Problem $3$: Complex FSA $(60$ pts$)$

a$)(2$pt$)$ Design a FSA that will recognize sentences such as $$

$$ Namely, the sentences should look like $$There$$s an THING$1$ on$/$in the THING$2$ on$/$in the THING$3...$ on$/$in the THINGn$,$ where THINGn is a thing, and where the maximum n can be arbitrarily large. Assume that words are fed to the FSA one at a time $($not a character at a time$),$ and your FSA may include one special transition that tests whether a word represents

a noun or not.

b$)(2$pts$)$ Design an FSA that recognize sentences such as $$The mouse the cat the dog chased ate lived in the house that Mary built.$,$ namely $$ANIMAL$1$ ANIMAL$2$ ANIMAL$3...$VERBED$3$ VERBED$2$ VERBED$1$ lived in the PLACE$1$ which Mary built.$$ Assume that n $<=3$ and that you have two special transitions available, one that tests whether a word represents an animal, and the other that tests whether a word is a verb.

c$)(2$pts$)$ For part $($b$),$ would it be possible to design an FSA that would work to arbitrary depth n$?$ Why or why not? What is different between the FSA is part $($a$)$ and in part $($b$)?$