How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

Question

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL.

Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$.

When I separate to cases, looking at the homogeneous case, by choosing either $w_0$ or $w_2$ I can't disprove the lemma, because the number of $c$ is always less/equal then the maximum and greater/equal then the minimum.

Any help?

Answer 1

Idea

The pumping lemma for context-free languages is not useful since M is "pumpable" with pumping length $p=2$. Instead, we will select a word in $\mathcal M$ that has less number of $a$'s and almost equal number of $b$'s and $c$'s, using Ogden's lemma to force its "pumpable part" to include at least one $a$.

Pump $s=a^pb^{3p+1}c^{3p}\in\mathcal M$

Suppose $\mathcal M$ is context-free and $p\ge1$ be the pumping constant for $\mathcal M$ in Ogden's lemma.

Mark all $p$ $a$'s in $s$. By Ogden's lemma, $s=uvwxy$, where $u,v,w,x,y$ are strings such that:

1. $\#_a(vx)\ge1$.
2. $uv^nwx^ny\in\mathcal M$ for all $n\ge0$.

In $s$, all $a$'s in $s$ are at the left and $v$ is to the left of $x$. So we know either $v$ is empty or $\#_a(v)\ge1$, thanks to condition 1.

There are two cases.

• $v$ or $x$ contains different symbols.
  Then $uv^2wx^2y\notin \mathcal M$, since it contains symbols in the wrong order.
• Otherwise, neither $v$ nor $x$ contains different symbols.
  In particular, $v$ is empty or contains $a$ only.

  • Suppose $x$ is nonempty and contains $c$ only.
    Consider $s'=uv^3wx^3y$.

    • $\#_a(s')\le \#_a(u^3v^3w^3x^3y^3)= 3\#_a(s)=3p$
    • $\#_b(s')=\#_b(s) = 3p + 1$
    • $\#_c(s')=\#_c(s) + 2\#_c(vx) \ge 3p + 2\gt \max(3p, 3p+1)$

    So, $s'\notin \mathcal M$

  • Otherwise, $x$ does not contain $c$.
    Consider $s''=uv^{3p+1}wx^{3p+1}y$.

    • $\#_a(s'')\ge\#_a(v^{3p+1}x^{3p+1})\ge 3p+1$
    • $\#_b(s'')\ge\#_b(s) = 3p + 1$
    • $\#_c(s'')=\#_c(s) = 3p\lt \min(3p+1, 3p+1)$

    So, $s''\notin \mathcal M$

So, in all cases, $uv^nwx^ny\not\in M$ for some $n$. This contradicts Ogden's lemma.

Hence, $\mathcal M$ is not context-free.

Exercises

1. Check that $\mathcal M$ satisfies the pumping lemma for context-free languages with pumping length $p=2$.

2. Show that $\mathcal J =\{a^ib^jc^k \mid \min(i,k)\le j\le\max(i,k)\}$ is not context-free.

Answer 2

This is incorrect -- it does not take into account that $|vwx|$ can have more than $p$ characters. I will try to salvage it in the coming days.

Ogden's lemma seems to work better here. Suppose $L$ is context-free and let $p$ be the lower limit. Choose $s = a^{p}b^{p+2}c^{p+1}$ and mark all the $a$'s (the first $p$ symbols of $s$). Then by Ogden's lemma we should be able to write $s = uvwxy$ such that:

1. $vx$ has at least one marked position: this means that $v$ contains at least one $a$.

2. $vwx$ has at most $p$ marked positions: this is trivially true because $s$ has exactly $p$ marked positions.

3. $uv^nwx^ny \in L$ for all $n \geq 0$.

Due to our choice of $s$ and markings, $vwx$ will consist of at least one $a$ and possibly some $b$'s. Hence, $uv^3wx^3y$ will have

• at least $p+2$ symbols $a$;
• at least $p+2$ symbols $b$;
• exactly $p+1$ symbols $c$ (same as $s$).

Therefore, condition (3) above fails, so $L$ cannot be context-free.

Answer 3

I want to give you some intuition why your language isn't CFL. We know that every CFL there exist atleast one PDA. If PDA doesn't exist that means languages definitely not CFL. So I give you intuitive proof with respect to PDA design, whether the design of PDA is possible or not:

$L_1 = \{ a^i b^j c^k | k ≥ min(i,j) \}$

Here number of $c$ is greater than minimum of number of $a$ and number of $b.$ So, we can say that if number of $c$ is greater than number of $a$ or if number of $c$ is greater than number of $b$, we accept. i.e.,

$L_1 = \{ a^ib^jc^k | k ≥ i$ or $k ≥ j\}$

The OR condition here means even though we need to do two checks, we can accept in either case and hence using non-determinism we just need a PDA to accept $L_1$ (we non-deterministically check if $k \geq j$ and if $k \geq i$). So, $L_1$ is a CFL but not DCFL.

$L_2 = \{ a^i b^j c^k | k \leq max(i,j) \}$

This can be rewritten as $L_2= \{ a^ib^jc^k | k \leq i$ or $k \leq j \}$

So, similarly $L_2$ is also CFL but not DCFL.

By the above two languages $L_1,L_2$ you can prove that your language $\{a^ib^jc^k ~|~k\le\max(i,j) ~and~ k\ge\min(i,j)\}=\{a^ib^jc^k ~|(~k\leq i ~Or~ k \leq j) ~and~ (k \geq i ~Or~ k \geq j\}$

isn't CFL because here is needed two comparison,making it CSL.

^{If $L_2 = \{ a^i b^j c^k | k \geq max(i,j) \}$ then alone $L_2 = \{ a^ib^jc^k | k ≥ i$ AND $k ≥ j\}$ is CSL.}