Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

Question

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.

Answer 1

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.