# (Non) Context Free language?

In an exam question it is asked to identify if the given language is Context-Free, Non Context Free or Regular. This is the question :

In my opinion this language is not a CFL since w doesn't belong to L', meaning that it belongs to not(L') which is all words (a^n b^n c^n) which is not CFL.

Apparently my answer is not right and I really don't understand why... Is this question a "trap" because i,j,k > 0 and not >= ? Meaning that a word (b^n c^n) is in L ? Looks like I'm lost !

I really need your help and explantions.

It helps to think of $$L$$ as having two parts.

• First part: $$L_1$$ is all strings not in the form $$a^i b^j c^k$$. We can write this with the regular expression $$\neg [a^* b^* c^*]$$, so it's regular.
• (I've been informed this notation isn't universal, so to spell it out: it's the complement of the regular language $$a^* b^* c^*$$, and the complement of a regular language is regular.)
• Second part: $$L_2$$ is all strings in the form $$a^i b^j c^k$$ such that the given conditions on $$i, j, k$$ are not fulfilled.

The given conditions are that $$i, j, k$$ are all different. So how can those conditions be violated? Either $$i=j$$, or $$j=k$$, or $$i=k$$. We can call these three options $$L_{2a}$$, $$L_{2b}$$, and $$L_{2c}$$ if you want.

Let's take just one of them as an example; the others work the same way. $$L_{2a}$$ is all strings of the form $$a^i b^i c^k$$. Can you write a regular expression for this? How about a CFG? (The answers are no, and yes: in fact, this is one of the classic examples for what a CFG can do that a regular expression can't.)

Now, since $$L_{2a}$$, $$L_{2b}$$, and $$L_{2c}$$ are all context-free, their union ($$L_2$$) is also context-free. And since $$L_1$$ is regular, it's also context-free. So $$L$$, as the union of two context-free languages, is context-free.

• Great, amazing answer, thanks a lot ! – Elia Dratwa Mar 5 '19 at 4:33
• Really like the way you explained that – Elia Dratwa Mar 5 '19 at 4:34
• However, thinking about it, for the second part, it's eiter i = j or j = k or i = k OR i = j = k, meaning that there is also the form a^i b^i c^i which is not CFL. Making the union of those 4 sub options not especially a CLF. Am I completely lost ? – Elia Dratwa Mar 5 '19 at 4:39
• @EliaDratwa You're right that $a^i b^i c^i$ isn't context-free. But $a^i b^i c^k$ is, and $a^i b^i c^i$ is a subset of that, so you don't have to care about it. – Draconis Mar 5 '19 at 4:41
• Ok, got it, Thanks a lot ! – Elia Dratwa Mar 5 '19 at 4:44

Not L' isn't just all words a^nb^nc^n, it also contains words that don't fit the a^nb^mc^k pattern, like "cab" or "bac", etc. It also contains the words a^nb^nc^m, etc. Try writing a CFG for it.

• Not really sure about that, moreover, words like cccaaabbb or bbaacc have to be recognize aswell... Maybe it's just me missing, don't understand something – Elia Dratwa Mar 5 '19 at 4:43