$1.$ One perspective of this class is that we are developing a theory of representation, or definability. For finite sets, this is easy, but it becomes more challenging for infinite languages. This class is really about the ability of different finite objects to understand and describe infinite sets.

$($a$)(5$ points$)$ Prove every finite language is regular.

$($b$)(5$ points$)$ Suppose we relax our definition of DFA too much. We define a DIA to be exactly like a DFA except $|$Q$|=|$N$|,$ and $\backslash$delta $,$ F are adjusted appropriately. Prove that every language is decidable by a DIA.

$2.$ Give an NFA, DFA, and regular expression for the following languages. Your solution doesn$$t have to be minimal, but it may assist the TA in grading. These may seem similar, but I promise they have different solutions. Here int$($w$,2)$ converts the binary string w to a number and you may suppose int$(\backslash$epsi $,2)=0.$

$($a$)(6$points$)$NFA$,$DFA,RegexforL$1=\{1$n $|$n$3($mod$4)\}$

$($b$)(6$points$)$NFAandDFAforL$2=\{$w in $\backslash$Sigma $|$int$($w$,2)3($mod$4)\}$

$($c$)(6$points$)$DFAforL$3=\{$w in $\backslash$Sigma $|$int$($w$,2)3($mod$5)\}$

$3.(6)$ Let D be a DFA with exactly one accept state which decides language L$.$ Prove thatifx,y in Lthen$$z in $\backslash$Sigma $$ thatxz,yzarebothinLorbothnotinL. $($Hint$,$ induction on the length of z$)$

$4.(6)$ Suppose that you are given two DFAs D$1,$D$2$ which use the same alphabet and have n$,$m states respectively. Prove you can determine L$($D$1)=$ L$($D$2)$ only by testing D$1,$D$2$ on all strings up to some length k$.$ What is k$?($Hint$,$ consider the contrapositive. If L$($D$1)=$ L$($D$2),$ then there is a shortest string they disagree on$.$ What is an upperbound on the length of this string? For a second hint, consider the DFA cartesian product at the end of lecture L$01$B$.$ This problem is cool because you can prove the DFAs have identical behavior on infinitely many inputs, all of them, just by testing them on a few.$)$