1
$\begingroup$

I have a question about the pumping lemma for context-free languages. I understand the conditions of the pumping lemma.

Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma. $z=uvwxy$ with conditions:

  1. $|vwx|\leq n$

  2. $|vx|\geq 1$

  3. $\forall i >0, \exists z= uv^iwx^iy \in L$

But i need to know what are the possible cases for the $vx$, alternatively $vwx$, so when pumped we can argue it does not belong to the language, and if the # symbol affects the assumption?

$$L = \{u\#v\#w \mid u,v,w \in \{a,b,c\}^* , |u|_a = |v|_b = |w|_c\}$$

From what I understand, I can assume that $v$ or $y$ are only in first part $u$ or second $v$ or $w$, but also $vxy$ can be in between $a$'s and $b$'s, including the $\#$ between them.

$\endgroup$
2
  • $\begingroup$ Since the pumping lemma can have different notations, you should remind us of the ones you are using before asking your question, otherwise it is not very clear what are $x$ and $y$ or even if the $v$ is the same as in the language you define. $\endgroup$
    – Nathaniel
    Feb 18 at 22:06
  • $\begingroup$ i did add the lemma sorry $\endgroup$ Feb 18 at 22:18
3
$\begingroup$

Condition 3 as in the question, "$\forall i >0, \exists z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we "pump down" $uvwxy$ to $uwy$.

The difficulty of applying pumping lemma comes from, indeed, recognizing "the possible cases for the $vx$" correctly and organizing them in a way that is easy to pump the word up or down to be not in the language.

Since the condition on the words in $L$ is about the number of $a$s, $b$s or $c$s in them, we will classify $v$ and $x$ also in the number of $a$s, $b$s or $c$s in them. For pumping length ${n}$, we will let $z$ be $a^n\#b^n\#c^n$, the simplest word in $L$ with length at least $n$.

  1. If either $v$ or $x$ contains $\#$, $uwy$ will have less than 2 $\#$s, hence not a word in $L$.

  2. Otherwise, all symbols in $v$ must be the same, and all symbols in $x$ must be the same.

    Since we have 3 symbols, $a,b,c$ in $z$, (at least) one of $a,b,c$ will be missing in $vx$.

    The number of $a$s, the number of $b$s and the number $c$s in $uvwxy$ are the same. Since $uv^2wx^2y$ is $vx$ "more than" $uvwxy$, the number of that missing symbol in $uv^2wx^2y$, will be less than both the number of $s_v$ in it if $s_v$ is the symbol in $v$, and the number of $s_x$ in it if $s_x$ is the symbol in $x$. Since $|vx|\ge1$, either $s_v$ or $s_x$ exists. This means $uv^2wx^2y$ is not in $L$.

Since we can always pump $z$ outside of $L$, $L$ does not satisfy the pumping lemma. So, $L$ cannot be context-free.


I can assume that v or y are only in first part $u$ or second $v$ or $w$ but also $vxy$ can be in between $a's$ and $b's$ including the $\#$ between them.

I don't quite understand your statement literally.

However, apparently, you wanted to say that given $z$, there are various possibilities for $u$, $v$, $w$, $x$ and $y$, which is totally true. Only the usage of some abstraction or general property (which might be simple or complicated) will enable us to cover all of them. That is where the fun or wisdom are.

$\endgroup$
2
  • $\begingroup$ Thank you i now understanded the argument and yes the question is formed in a wrong way. its my first time sorry $\endgroup$ Feb 20 at 16:10
  • 1
    $\begingroup$ Welcome! No problem at all. I made lots of mistakes the first times. $\endgroup$
    – John L.
    Feb 20 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.