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 $$There$$s a flea on the speck on

the frog on the bump on the branch on the log in the hole in the bottom of the sea.$$ 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$)?$