2
$\begingroup$

I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$

where $m,n,o$ are non-negative integers.

I have to find whether the language is regular or not.

My attempt:

I feel it should be non regular. For it to be regular, we'd have to keep track of how many $a's$, $b's$ and $c's$ we have seen. But the problem is that there can be infinitely many values of $a$, $b$ and $c$ for the given constraint, and we can't "remember" that number with finitely many states.

On the other hand, I also think that if we take the complement of the language i.e

$$L = \{a^mb^nc^o| \, m + n + o <= 5\}$$ We know that this is regular because there are finite number of solutions for the constraint. Now, since regular languages are closed under complement, we can say the former is also regular.

Which one of these methods is correct? I tried to prove it using Pumping Lemma, but to no avail.

$\endgroup$
  • 1
    $\begingroup$ Your two $L$'s are not complements of each other. $\endgroup$ – Yuval Filmus Sep 11 '18 at 6:07
  • $\begingroup$ But you don't care if there are infinitely many a, b, or c. If there are six a's then the string is in the language and you can stop counting. $\endgroup$ – gnasher729 Sep 11 '18 at 7:39
  • $\begingroup$ Yeah, I realised the complement is incorrect and also that we don't have to remember all the a's,b's and c's we've seen. So the only way to prove this would be to construct a regex as below or a DFA I suppose? $\endgroup$ – Gokul Sep 11 '18 at 8:34
  • $\begingroup$ Following the algorithm outlined by David Richerby, you should be able to demonstrate that the set of strings in which the sum of the counts of $a$, $b$, and $c$ is greater than 5 is a regular language, regardless of how the letters are interleaved. That's a somewhat more interesting lamguage. :-) $\endgroup$ – rici Sep 11 '18 at 20:05
  • $\begingroup$ @YuvalFilmus It's the complement relative to $a^*b^*c^*$, which is enough, since regular languages are closed under difference. $\endgroup$ – David Richerby Sep 11 '18 at 22:08
3
$\begingroup$

$L$ is regular.

Here is a proof as hinted by your second method, which points out that we may take advantage of the fact that regular languages are closed under complement. Another useful fact is regular languages is closed under intersection. Let $F=\{a^mb^nc^o| m,n,o\in\Bbb Z_{\ge 0}, m+n+o\le 5\}$. As a finite language, $F$ is regular. Let $H = \{a^mb^nc^o| m,n,o\in\Bbb Z_{\ge 0}\}$. As expressed by the regular expression $a*b*c*$, $H$ is regular. Since $L= H\cap\overline F$, $L$ is regular.

We can also see that $L$ is regular by the following one-line regular expression that expresses $L$. It is wrapped into multiple lines for easier reading.

$ ((a\{6,\}|a\{5,\}b+|a\{4,\}b\{2,\}|a\{3,\}b\{3,\}|a\{2,\}b\{4,\}|a+b\{5,\})c*)|\\ ((a\{5,\}|a\{4,\}b+|a\{3,\}b\{2,\}|a\{2,\}b\{3,\}|a+b\{4,\}|b\{5,\})c+)|\\ ((a\{4,\}|a\{3,\}b+|a\{2,\}b\{2,\}|a+b\{3,\}|b\{4,\})c\{2,\})|\\ ((a\{3,\}|a\{2,\}b+|a+b\{2,\}|b\{3,\})c\{3,\})|\\ ((a\{2,\}|a+b+|b\{2,\})c\{4,\})|\\ (a+|b+)c\{5,\}|\\ c\{6,\} $

Now that we have shown $L$ is a regular, the first method must be incorrect. In fact, we do not have to keep track of how many a′s, b′s and c′s we have seen. All we need is to make sure that the total number of them is greater than 5. There is a difference between these two requirements.


By the same argument, we can see easily that for any integer $k$, $L_k = \{a^mb^nc^o|m,n,o\in\Bbb Z_{\ge0},\,m + n + o > k\}$ is a regular language.

Here is another similar fact. For any integer $s$ and $t$, $L_{s,t}=\{a^mb^nc^od^p|m,n,o,p\in\Bbb Z_{\ge0},\,m + o > s, n+p >t\}$ is a regular language.

$\endgroup$
  • $\begingroup$ I just realised my complement method doesn't work, as Yuval pointed out. So I suppose the only way to solve it would be to construct a regex? $\endgroup$ – Gokul Sep 11 '18 at 8:23
  • $\begingroup$ Here is another way. $L$ is regular because it is the intersection of two regular languages, $\{w\mid\#w\gt5\}$ and $a^*b^*c^*$. $\endgroup$ – Apass.Jack Dec 27 '18 at 1:25
3
$\begingroup$

Your intuition should be that the language is regular. You don't need complete knowledge of the numbers of $a$s, $b$s and $c$s. You can count them off as "Zero, one, two, three, four, five, more-than-five-and-I-don't-care-by-how-much" which is a finite amount of information.

$\endgroup$

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.