0
$\begingroup$

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 :

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Great, amazing answer, thanks a lot ! $\endgroup$ Commented Mar 5, 2019 at 4:33
  • $\begingroup$ Really like the way you explained that $\endgroup$ Commented Mar 5, 2019 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$ Commented Mar 5, 2019 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
    Commented Mar 5, 2019 at 4:41
-1
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Mar 5, 2019 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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