How can I prove this language is regular?

Question

I'm trying to prove if this language:

L = { w={0,1}* | #₀(w) % 3 = 0 } (number of 0's is divisble by 3)

is regular using the pumping lemma, but I can't find a way to do it. All other examples I got, have a simple form or let's say a more defined form such as w = a^xb^yc^z etc.

Answer 1

• A language is regular if and only if some nondeterministic finite automaton recognizes it.
• Automaton is a finite state machine.

We have to build an automaton that regonizes L.
For each state, thinking like:

• "Where am I?"
• "Where can I go to, with some given entry?"

So, for L = { w={0,1}* | #0(w) % 3 = 0 }
The possibilites (states) are: The remainder (rest of division) is 0, 1 or 2. Which means we need three states. Let q0,q1 and q2 be the states that represent the remainderes 0,1 and 2, respectively.

q0 is the start and final state.
Now, for "0" entries, do the math #0(w)%3 and go to the aproppriated state.
Transion functions:
f(q0, 0) = q1
f(q1, 0) = q2
f(q2, 0) = q0

For "1" entries, it just loops wherever it is, 'cause it doesn't change the machine state.
f(qx, 1) = qx

The pumping lemma proves if some language is not regular.
Here is a good book for theory of computation: Introduction to the Theory of Computation 3rd Edition by Michael Sipser.

Answer 2

Any string in this language with at least three characters in it has this property: either the string has a "1" in it, or there are three "0"s in a row.

If the string contains a 1, then you can split it as in the pumping lemma and set y equal to some 1 in the string. Then obviously the strings xyz, xyyz, xyyyz, etc. are all in the language because all those strings have the same number of zeros.

If the string does not contain a 1, it contains three 0s in a row. Setting y to those three 0s, it should be obvious that xyz, xyyz, xyyyz, etc. are all in the language because you're adding three 0 characters each time, so you always have a number of 0s divisible by 3.

@justhalf in the comments is perfectly correct; the pumping lemma can be used to prove that a regular language can be pumped or that a language that cannot be pumped is not regular, but you cannot use the pumping lemma to prove that a language is regular in the first place. Mea Culpa.

Instead, here's a proof that the given language is regular based on the Myhill-Nerode Theorem:

Consider the set of all strings of 0s and 1s. Divide these strings into three sets:

E₀, all strings such that the number of 0s is a multiple of three,

E₁, all strings such that the number of 0s is one more than a multiple of three,

E₂, all strings such that the number of 0s is two more than a multiple of three.

Obviously, every string of 0s and 1s is in one of these three sets.

Furthermore, if x and z are both strings of 0s and 1s, then consider what it means if the concatenation xz is in L:

1. If x is in E₀, then xz is in L if and only if z is in E₀

2. If x is in E₁, then xz is in L if and only if z is in E₂

3. If x is in E₂, then xz is in L if and only if z is in E₁

Therefore, in the language of the theorem, there is no distinguishing extension for any two strings in the same one of our three E_i sets, and therefore there are at most three equivalence classes. A finite number of equivalence classes means the language is regular.

(in fact, there are exactly three equivalence classes, but that isn't needed)

Answer 3

I don't think you can use pumping lemma to prove that a language is regular. To prove a language is regular, you just need to give a regular expression or a DFA. In this case the regular expression is quite easy:

1*(01*01*01*)*

(proof: the regular expression clearly does not accept any string which has the number of 0's not divisible by 3, so we just need to prove that all possible strings which has the number of 0's divisible by 3 is accepted by this regular expression, which can be done by confirming that for strings that contain 3n 0's, the regular expression matches it since 1^n₀01^n₁01^n₂01^n₃...01^n_3n-201^n_3n-101^n_3n has the same number of 0's and the n_k's can be substituted so that it matches the string, and that this format is clearly accepted by the regular expression)

Pumping lemma cannot be used to prove that a language is regular because we cannot set the y as in Daniel Martin's answer. Here is a counter-example, in a similar format as his answer (please correct me if I'm doing something fundamentally different from his answer):

We prove that the language L = {w=0ⁿ1^p | n ∈ N, n>0, p is prime} is regular using pumping lemma as follows: note that there is at least one occurrence of 0, so we take y as 0, and we have xy^kz = 0^n+k-11^p, which still satisfy the language definition. Therefore L is regular.

But this is false, since we know that a sequence with prime-numbered length is not regular. The problem here is we cannot just set y to any character.