Problem $2($Practice with DFAs$)$

$10$ Points

$(5$ pts$)$ First, write out a formal description of this finite automaton $($DFA$)$ using the notation

$M=(Q,,,q_0,F)$ that we saw in class. Then describe what language it recognizes.

PS$1,$ Page $1$

$(5$ pts$)$ Let $=\{\left[\begin{array}{c}0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}1\\ 1\end{array}\right]\}$ be an alphabet.

When given a string win${}^{*}$ consider the top row as a number written in binary and consider

the bottom row a second number written in binary.

So for example the string $w=\left[\begin{array}{c}1\\ 0\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]$ represents the number $5$ on top and $2$ on

the bottom.

Let $L=\{\begin{array}{c}w|win{}^{*}\end{array}$ and the top binary number in $w$ is greater than the bottom number in $\{$:$w\}.$

Construct a DFA for the language $L.$