Formally proving that $\{ L = { {a^i}{b^j}{c^k}, j = \min(i,k), i, k > 0\} } $ is context-free

Question

Please no hints.

I need to formally prove that $\{ L = { {a^i}{b^j}{c^k}\mid j = \min(i,k),\: i, k > 0\} } $:

At first my idea was to use pumping lemma, so I tried to study where $\\|vwx|\ $falls but it seems that for some cases the pumped string is accepted, this led me to thinking that pumping lemma couldn't work, so I separated $ \ L = L1 \bigcup L2 $, because CF languages are closed under union, with :

$\{ L1 = { {a^i}{b^i}{c^k} | 0 < i < k\} } $

$\{ L2 = { {a^i}{b^k}{c^k} | 0 < k < i\} } $

The problem is also with L1 and L2 I can't work this out with pumping lemma. Actually I even can't decide a good $p$ for

$\\|vwx|\ = p$

I tried using concatenation with ${a^+}{b^+}$ but then I get stuck. I tried to write a grammar for both $L1$ and $L2$ but was no use. Can someone show me the way this exercise is meant to be done? I would really appreciate it.

Answer 1

The language is not context-free, and that can be demonstrated with the pumping lemma.

Suppose $L$ were context-free. Take the sentence $\omega=a^pb^pc^p$, which is certainly in $L$. The pumping lemma says that if $L$ is context-free, then $\omega$ contains a substring $vwx$ whose length is less than $p$ which can be replaced with $v^nwx^n$ for any integer $n\ge 0$ to yield another sentence in the language.

The length restriction means that $vwx$ contains at most two different symbols, since it cannot span from $a$ to $c$. In order for the replacement $vwx\to vvwxx$ to produce a sentence in $L$, it's necessary for $v$ and $x$ to be repetitions of a single symbol; otherwise $vv$ (resp. $xx$) would contain either $ba$ or $cb$, which cannot be substrings of a sentence in $L$. So that reduces to the following cases:

1. $v$ and $x$ are repetitions of $a$ or both repetitions of $c$. Chose $n=0$ so that the replacement is $vwx\to w$. Since the count of $b$ is not reduced, it no longer has the same length as the minimum.

2. $v$ and $x$ are both repetitions of $b$. Chose $n=2$; now there are more $b$ than either $a$ or $c$.

3. One of $v$ and $x$ consists of repetitions of $b$ and the other one doesn't. Choose $n=2$. Now there are more $b$ than there are of whichever of $a$ and $c$ was not increased.

Consequently, the sentence $a^pb^pc^p$ cannot be pumped, contradicting the assertion that $L$ is context-free.