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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Your two $L$'s are not complements of each other. $\endgroup$ Commented Sep 11, 2018 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$ Commented Sep 11, 2018 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$ Commented Sep 11, 2018 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$ Commented Sep 11, 2018 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$ Commented Sep 11, 2018 at 22:08

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Sep 11, 2018 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$ Commented Dec 27, 2018 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.