Is it possible to make a PDA for $\{ ww : w \in \{ 0,1 \}^* \}$?

Question

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$.

Answer 1

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$.