- Thread starter
- #1

- Apr 14, 2013

- 4,047

Given the language $L$=$\{m^{(x)}: m$ is a symbol and $x$ is a perfect square$\}$, I have to show that L is not context-free using the Pumping Lemma.

First, we assume that L is context-free. So, from the pumping lemma there is a pumping length $p$. Let $s=m^{(p)}$, that can be divided into $uvxyz$.

How can I continue? How can I find something so that I can conclude that one of the conditions of Pumping Lemma is not satisfied?

Conditions of Pumping Lemma:

1) $ \forall i\geq 0$ $uv^ixy^iz$ $\epsilon$ $L$

2) $ |vy|>0$

3) $|vxy| \leq p$