Problem 1: \\

Give, without proof, a CFG that generates each of the following languages
\begin{enumerate}
\item $L_1 = \{ w \in \{0, 1\}^* | \text{ $w$ is a palindrome}\}$
\item $L_2 = \{ w \in \{0, 1\}^* | \text{ in every prefix of } w \text{ the number of 0's is at least the number of 1's} \}$ 
\end{enumerate}

Problem 2: \\

Provide a  deterministic push-down automata that recognizes the following language $L$ over the alphabet $\Sigma = \{0,1\}$:
\[ L = \{w | \text{ $w$ has exactly half as many 0's as 1's.}\} \]

Problem 3: \\

For any language $A$, let $PREFIX(A)=\{v|vu\in A\textrm{ for some non-empty string }u\}$, i.e.\ the set of proper prefixes of strings in $A$. Show that the class of context-free languages is closed under the $PREFIX$ operator.