Problem 1: \\
\begin{enumerate}
    \item Prove that the set of Context-Free Languages is not closed under the complement operator. 
    \item Prove that the set of Deterministic Context-Free Languages is not closed under the union operator.
    \item If $A$ and $B$ are languages, define \[A\circ B=\{xy|x\in A\textrm{ and }y\in B\textrm{ and }|x|=|y|\}.\]
Given $A$ and $B$ are regular languages, argue whether $A\circ B$ is a CFL.
\end{enumerate}

Problem 2: \\
Let \[L_1 = \{w\in{1,\#}^*| w =t_1\#t_2\# \dots \#t_k\ \text{for}\ k \ge0,\  \text{each}\ t_i \in 1^*,\ \text{and}\ t_i \not = t_j\ \text{whenever}\  i \not= j\}.\]
\begin{itemize}
    \item Prove that $L_1$ is not a Context-Free language.
    \item Prove that $L_1$ is a Turing-Decidable language. If you choose to do so by showing an accepting Turing Machine $M_1$ such that $L_1=L(M_1)$, you need to show a proof of correctness.
\end{itemize}

Problem 3: \\
Let $L_2 = \{w\in \{0,1\}^{*}| w =w^R\text{ and there are the same number of 0's as 1's in }w\}$.
\begin{itemize}
    \item Prove that $L_2$ is not a Context-Free language.
    \item Prove that $L_2$ is a Turing-Decidable language. If you choose to do so by showing an accepting Turing Machine $M_1$ such that $L_1=L(M_1)$, you need to show a proof of correctness.
\end{itemize}