- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hello! ![Eek! :eek: :eek:](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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$
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$