# Context-freeness of $\{a^nb^mc^k \mid n \leq m \leq k\}$ and its complement

Was analysing old exam, still, even in home condition can answer this:

Determine which of the following languages over the alphabet $\{a,b,c\}$ are context-free. Prove the claim.

(a) $L_1 = \{a^nb^mc^k \mid n \leq m \leq k\}$,

(b) $L_2 = \{a,b,c\}^* \setminus L_1$, that is, $L_2$ is the complement of $L_1$ from (a).

Any help would be appreciated, it doesn't seem like CFL to me, but I struggle to apply pumping lemma here.

The language $L_1$ is not context-free, and you can show this using the pumping lemma. Try to pump the word $a^nb^nc^n$ where $n$ is large enough.

The language $L_2$, in turn, is context-free. This is because we can write it as a union of context-free languages:

• Words not of the form $a^*b^*c^*$.
• Words of the form $a^nb^mc^k$ where $n>m$.
• Words of the form $a^nb^mc^k$ where $m>k$.
• Thanks. Got answer 8 in morning, at 9 had redo of exam... Surprise, surprise - this question was there too. 1) part would possibly figure out myself, was very close independently. But for 2) - warmest thanks. Wouldn't think myself. – Timo Junolainen Jan 9 '17 at 13:33