Is it possible to make a PDA for $\{ ww : w \in \{ 0,1 \}^* \}$? Consider the language $L = \{ ww : w  \in \{ 1,0 \}^* \}$.
I know it's easy to make a PDA for $\{ w w^\text{R} : w \in \{ 0,1 \}^* \}$ where $w^{\text{R}}$ is the reverse of $w$, but I can't think of a PDA that recognises the language $L$.
 A: This is not possible.  I will outline a proof that relies on the Pumping Lemma for Context Free Languages:

If $L$ is a context free language, then there is a number $p$ such that each word $s \in p$ of length at least $p$ can be decomposed as $s = uvwxy$ where
  
  
*
  
*$| vwx | \leq p$;
  
*$ | vx | \geq 1$;
  
*$uv^nxy^nz \in L$ for all $n \geq 0$.
  

Suppose that $p \geq 1$ is a pumping length for the language $L = \{ ww : w \in \{ 
\newcommand{\myone}{{\mathtt{1}}}
\newcommand{\mynil}{{\mathtt{0}}}\mynil , \myone \}^* \}$, and consider the string $s = \mynil^p\myone^p\mynil^p\myone^p \in L$.  Since $| s | = 4p > p$ we may decompose $s$ as $uvwxy$ as above.  Note that since $| vxy | \leq p$ it must be that $vxy$ is of one of the following forms:


*

*$\mynil^k$ for some $1 \leq k \leq p$;

*$\mynil^k \myone^\ell$ for some $1 \leq k , \ell < p$;

*$\myone^\ell$ for some $1 \leq \ell \leq p$;

*$\myone^\ell \mynil^k$ for some $1 \leq k , \ell < p$.


We can go through these cases, and show that there is a "pump" after which we get a string not in $L$.  For example, the first case breaks down into two very similar subcases (depending on whether the substring $vxy$ is in the first group of $\mynil$s, or the second).  For the first subcase, we have $u = \mynil^i$, and $z = \mynil^{p-i-k} \myone^p \mynil^p \myone^p$.  Furthermore $v = \mynil^r$, $x = \mynil^s$, $y = \mynil^t$ where $r + s + t = k$ and either $r >0$ or $t > 0$ (or both).  It is not difficult to determine that $$uv^0xy^0z = u x z = \mynil^i \mynil^s \mynil^{p-i-k} \myone^p \mynil^p \myone^p = \mynil^{p-r-t} \myone^p \mynil^p \myone^p$$ cannot be in $L$.
