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$ = $w^R$ and $|w|$ is even}\}$ ($w^R$ denotes the reverse of w) %Ans: S->0S0 | 1S1 | epsilon
\item $L_2 = \{ w \in \{0, 1\}^* | \text{ in every prefix of } w \text{ the number of 0's is no more than the number of 1's} \}$ 
\end{enumerate}

Problem 2: \\

Design a \textit{deterministic} pushdown automaton for the language
$L = \{ w \in \{a, b\}^* | \text{w starts and ends with the same symbol}\}$ and provide a proof of correctness. (note: the empty string should be accepted)

Problem 3: \\

For an alphabet $\Sigma = \{a,b\}$, show that the language consisting of strings that have an equal number of a's and b's but no substring of the form abba is context-free. (Hint: you may assume that the language of all strings with no substring abba is regular).

Problem 4: \\

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.