Problem $1$: $(25$ points$)$ Let $A=\{a_1,a_2,$dots,$a_{1403}\}sub\{0,1{\}}^{**}$ be a set of strings with $a_{i}in\{0,1{\}}^{**}$ for all $1i1403.$

Can one describe $A-\{\}$ by a regular expression? Why?

Can one describe $A^2=A*A$ by a regular expression? Why? $\{0,1{\}}^{1403}+\{0,1{\}}^{1403}$

Can one describe $A^{**}$ by a regular expression? Why?

Problem $2$: $(25$ points$)$ Let Lsub$\{0,1{\}}^{**}$ be the formal language of all strings that contain at least two $1\text{'}$s$.$

Provide a regular expression for $L.$

Provide a minimal DFA that describes $L^R$

strings that contain $at$ least

$(0,1)(0+1{)}^{**}\frac{1}{(0+1)}$

$L^R$

Problem $3$: $(25$ points$)$ Which one of the following formal languages are regular? Why?

$\{u$$$u|uin\{0,1{\}}^{**}\}sube\{0,1,$$${\}}^{**}.$

The set of all strings in $\{0,1{\}}^{**}$ having different number of zeros and ones.

Problem $4$: $(25$ points$)$ Consider the following $-$NFA describing a language $L$ and construct a minimal DFA describing $L^R($explicitly describe your method and write down the details of your computations$).$

$S_1{S}_2$

Figure $1$: The $-$NFA of Problem $4.$