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.

Thanks in advance.


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.

  • $\begingroup$ Great, amazing answer, thanks a lot ! $\endgroup$ – Elia Dratwa Mar 5 '19 at 4:33
  • $\begingroup$ Really like the way you explained that $\endgroup$ – Elia Dratwa Mar 5 '19 at 4:34
  • $\begingroup$ 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 ? $\endgroup$ – Elia Dratwa Mar 5 '19 at 4:39
  • $\begingroup$ @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. $\endgroup$ – Draconis Mar 5 '19 at 4:41
  • $\begingroup$ Ok, got it, Thanks a lot ! $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – Elia Dratwa Mar 5 '19 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.