Problem 1:\\
\begin{enumerate}[label=(\alph*)]
    \item Show by giving an example that if $M$ is an NFA that recognizes language $C$, swapping the accept and non-accept states in $M$ doesn't necessarily yield a new NFA that recognizes the complement of $C$. 
    \item Is the class of languages recognized by NFAs closed under complement? Explain your answer.
\end{enumerate}

Problem 2:\\
Let $\Sigma$ and $\Delta$ be finite alphabets of symbols. A \emph{homomorphism} is a function $h:\Sigma^* \rightarrow \Delta^*$ defined as follows:
\begin{enumerate}[label=(\alph*)]
    \item $h\left(\epsilon\right)=\epsilon$;
    \item For any $a\in \Sigma$, $h(a)\in\Delta^*$;
    \item For $a\in\Sigma^*$ such that $a=a_1a_2\ldots a_n$ with $n\geq 2$, 
    \[
    h(a)=h(a_1)h(a_2)\ldots h(a_n).
    \]
\end{enumerate}

That is, a homomorphism is a function from strings to strings that ``respects'' concatenation: for any $x,y\in \Sigma^*$, $h(xy)=h(x)h(y)$.

\emph{Example:} $h:\{0,1\}\rightarrow \{a,b\}^*$ where $h(0)=ab$ and $h(1)=ba$. Then $h(0011)=ababbaba$.

Given a homomorphism $h:\Sigma^*\rightarrow \Delta ^*$ and a language $L\subseteq \Sigma^*$, we define the homomorphism of a language $L$ as $h(L)=\{h(w) \mid w\in L\}\subseteq \Delta^*$.

Prove that the set of regular languages is \emph{closed under homomorphism}, that is, for any given regular language $L$, $h(L)$ is a regular language.

Problem 3:\\
We have already seen that the language
\begin{equation*}
    L = \left\{w \biggm| \begin{matrix} w \textrm{ contains an equal number of} \\ \textrm{occurrences of the substrings $01$ and $10$} \end{matrix}\right\}.
\end{equation*}
is regular. Now let
\begin{equation*}
    L' = \left\{w \biggm| \begin{matrix} w \textrm{ contains an equal number of} \\ \textrm{occurrences of the substrings $010$ and $101$} \end{matrix}\right\}.
\end{equation*}
Show that $L'$ is not regular. 

\textit{Hint:} if you're struggling to find a good string, consider one whose first segment contains only one of the substrings $010$ or $101$.

Problem 4:\\
Consider the language over the alphabet $\Sigma=\{x,y,z\}$:
\begin{enumerate}[label=(\alph*)]
    \item Let
    \begin{equation*}
        L_1 = \left\{x^kw \biggm| \begin{matrix} k \not = 1 \textrm{ and } w\in\Sigma^*\ \textrm{and the} \\ \textrm{first symbol of $w$ is not an `$x$'} \end{matrix}\right\}.
    \end{equation*}
    Prove that $L_1$ is regular. Showing a correct DFA/NFA/RegEx is sufficient.
    \item Let 
    \begin{equation*}
        L_2 = \{xy^nz^n \mid n \geq 0\}.
    \end{equation*}
    Prove that $L_2$ is not regular.
    \item Prove that $L = L_1 \cup L_2$ satisfies the pumping lemma property.
    \item Is $L$ regular? Provide a proof for your answer. 
    
    \textit{Hint:} it might help you to show that regular languages are closed under complement and/or intersection\dots
\end{enumerate}