Problem 1: \\
If A $\leq_{m}$ B and B is a regular language, does that imply that $A$ is a regular language? Prove why or why not?

Problem 2: \\
Consider the following languages. For each language, determine whether you can use Rice's Theorem to prove it is undecidable. If so, use Rice's Theorem to prove it is undecidable. If not, explain why you cannot use Rice's Theorem, and prove it is undecidable without using Rice's Theorem.

\begin{enumerate}
    \item[a.] $L_{inf} = \{ \langle M \rangle  \mid M \text{ is a TM and } L(M) \text{ is not finite} \}$

    \item[b.] $L_{101} = \{\langle M \rangle \mid M \text{ is a TM and 101} \in L(M)\}$

    \item[c.] $L_{seq} = \{ \langle M_1 \rangle, \langle M_2 \rangle \mid M_1, M_2 \text{ are TMs and } L(M_1) \subseteq L(M_2)\}$
\end{enumerate}

Problem 3: \\
\begin{enumerate}
\item[a.]
    For any natural number $k$, consider the language $A_{TM}^{(k)}$:
    $$A_{TM}^{(k)} = \{ \langle M, w \rangle \mid M \text{ is a TM with at most $k$ states and $M$ accepts $w$}\}$$
    Prove that there is some natural number $k$ where $A_{TM}^{(j)}$ is undecidable for all $j \geq k$.

\item[b.]
    A \emph{very sparse language} is a language $L$ over an alphabet $\Sigma$ that contains exactly one string of each length. If $L$ is a very sparse language, it contains the
    empty string, exactly one string of length one, exactly one string of length two, and so on. Prove that if $L$ is a very sparse language and is Turing-recognizable, then $L$ is
    decidable.

\end{enumerate}