Return to Answer

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

We can just use the standard pumping lemma for context-free language.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

• $vwx$ contains at least one letter other than $b$.
  Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Let $s=uwy=uv^0wx^0y$, which is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $s$ cannot be a palindrome.

• $vwx$ contains only $b$s.
  Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}-1$. Then $uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Exercise. Show the following language is not context-free. $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{b} \not= |w|_{c} \}\,. $$

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

Intuitively we cannot recognize $L$ using a pushdown automaton as the number of $b$'s has to be used twice, once in comparing against the number of $a$'s and once in comparing against the number of $c$'s. However, that is far from a proper proof.

We can just use the standard pumping lemma for context-free language for a rigorous proof.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

• $vwx$ contains at least one letter other than $b$.
  Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Let $s=uwy=uv^0wx^0y$, which is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $s$ cannot be a palindrome.

• $vwx$ contains only $b$s.
  Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}+1$. Then let $s=uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L\,.$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Here are two related exercises.

Exercise 1. Show the following language is not context-free. $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} > |w|_{b}\text{ and } |w|_{a} > |w|_{c} \}\,. $$

Exercise 2. Show the following language is not context-free. (Hint, Ogden's lemma.) $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{a} \not= |w|_{c} \}\,. $$

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

We can just use the standard pumping lemma for context-free language.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

• $vwx$ contains at least one letter other than $b$.
  Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Then $uwy$ is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $uwy$ cannot be a palindrome.

• $vwx$ contains only $b$s.
  Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}-1$. Then $uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Exercise. Show the following language is not context-free. $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{b} \not= |w|_{c} \}\,. $$

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

We can just use the standard pumping lemma for context-free language.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

• $vwx$ contains at least one letter other than $b$.
  Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Let $s=uwy=uv^0wx^0y$, which is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $s$ cannot be a palindrome.

• $vwx$ contains only $b$s.
  Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}-1$. Then $uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Exercise. Show the following language is not context-free. $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{b} \not= |w|_{c} \}\,. $$

Yes, you are right that $L$ is not context-free.

We can use the standard pumping lemma for context-free language.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a^pc^pb^{p+1}b^{p+1}c^pa^p\in L$. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

• $vx$ contain at least one $b$. Then $vx$ does not contain $a$. Let $s=uwy=uv^0wx^0y\in L$. However, it contain less $b$s than $t$ but no less $a$s than $t$. Note that the number of $b$s in all words in $L$ is even. That means $|s|_b\le|t|_b-2=|t|_a=|s|_a$.

• $vx$ does not contain $b$. WLOG, suppose $vx$ contains one $a$. Let $s=uv^3wx^3y\in L$. However, $|s|_a|\ge|t|_a+2\gt|t|_b=|s|_b$.

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

We can just use the standard pumping lemma for context-free language.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

• $vwx$ contains at least one letter other than $b$. 
  Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Then $uwy$ is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $uwy$ cannot be a palindrome.

• $vwx$ contains only $b$s.
  Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}-1$. Then $uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Exercise. Show the following language is not context-free. $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{b} \not= |w|_{c} \}\,. $$