P$1.(25$ points$)$ DFA Machine: consider the DFA below:

$1.$ write the formal description of the machine using the $5-$tuple format.

$2.$ What is the language of the $\{0,1\}$ alphabet that this machine recognizes. $($You may use the set notation or just English description.

P$2.(25$ points$)$ NFA Machine:

$1.$ Build an NFA over alphabet $\{$a$,$b$\}$ that accepts the language of strings that have no b$$s$,$ or else have one or more b$$s followed by a single a$.$

$2.$ write the formal description of the machine using the $5$ tuple format.

P$3.(30$ points$)$ Give NFA described below.

$1.$ What is the language this machine recognizes? Write you answer in this format: $$ L$=\{$w $|\}$

$2.$ write the formal definition of the Machine using the $5-$tuple

$3.$ Show the tree resulted from testing the input string $110.$ Will it be accepted or rejected?

P$4.(20$ points$)$ Give regular expressions generating the languages below

$1.\{$w$|$ w begins with a $1$ and ends with a $0\}$

$2.\{$w$|$ w contains the substring $0101($i$.$e$.,$ w $=$ x$0101$y for some x and y$)\}$

$3.\{$w$|$ every odd position of w is a $1\}$

$4.$ The language accepts all the strings except the empty string.