0
$\begingroup$

In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's lemma can be dispensed with.

This could be interpretted as $\{a^ib^jc^k: i,j,k\text{ are not all equal}\}$ correct? Can someone show that this is context-free without a lemma? Like making a CFG or PDA?

This is just for my own reference for learning.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think you're misunderstanding, the proof shows that $L$ is not context-free. You can construct neither a CFG nor a PDA for it. $\endgroup$ – aelguindy Nov 11 '16 at 2:34
  • 1
    $\begingroup$ Yes. I think it is, it can be written as a union of three CF languages, one which has $i \neq j$, another with $j \neq k$ and a third with $i \neq k$. $\endgroup$ – aelguindy Nov 11 '16 at 2:52
  • 2
    $\begingroup$ I don't understand. Your post mentions both $i\neq j$, $j\neq k$, $k\neq i$ (i.e., no pair of $i,j,k$ equal) and $i,j,k$ not all equal. Which are you asking about? These are two different languages. $\endgroup$ – David Richerby Nov 11 '16 at 9:55
  • $\begingroup$ Your title doesn't match the body of the question. Please edit one or the other to make them self-consistent. $\endgroup$ – D.W.♦ Nov 11 '16 at 15:47