Is this language context free and if it is which grammar generates it?

Question

$$L=\{\, w \in\{a,b,c\}^* :w=a^ib^jc^k, j=\max\{i,k\}\,\}$$

I think I proved it not context-free using pumping lema for CFL, but I'm not sure I'm doing it right. So, if someone knows grammar that generate this languge let me know =)

Answer 1

The language is not context-free.

Suppose that $\newcommand{\AA}{\mathtt{a}}\newcommand{\BB}{\mathtt{b}}\newcommand{\CC}{\mathtt{c}} p$ is a pumping length for $L$, and consider the string $s = \AA^p \BB^p \CC^p$. Then we may rewrite $s$ as $uvxyz$ where

1. $| vxy | \leq p$;
2. $| vy | \geq 1$; and
3. $u v^n x y^n z \in L$ for all $n \geq 0$.

Hint: Note that the substring $vxy$ is of the form $\AA^q \BB^r \CC^s$ for some $q,r,s \geq 0$ (not all zero). Show that the following cases are impossible:

• Each of $q,r,s$ is positive. (If so, note that $r$ must equal $p$);
• $q > 0$, $r = s = 0$. (If so, what happens when you pump $v,y$ more than one time?)
• $s > 0$, $q = r = 0$. (Similar to the above.)
• $r > 0$, $q = s = 0$. (Slightly different from the above two cases, but if so, what happens when you pump $v,y$ more than one time?)
• $s = 0$, $q,r > 0$. (What happens if you pump $v,y$ zero times?)
• $q = 0$, $r,s > 0$. (What happens if you pump $v,y$ zero times?)

Now note that there are no cases remaining!