Cheap and Secure Web Hosting Provider : See Now

# [Answers] Finding out if languages involving counting and modulo operations are regular

, ,
Problem Detail:

I am having trouble with the regularity of the two following languages:

i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$

ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$

To clarify this is stating that the (#(0's) - #(1's)) mod 3 = 0.

I know how to prove that the first language is regular without the n,m > 0 restriction but with it I am inclined to think that the language is not regular because we'd need to make sure there is at least one 1 and 0 b and in doing so would also have to "remember" the previous numbers of 0's and/or 1's. Which is not possible with a DFA.

My logic is similar with the second statement.

Is my logic right?

#### Answered By : Rick Decker

This is essentially @Yuval's hint, expressed in a slightly different way. You've said that you can prove $$L_u = \{0^n1^m\mid n, m \ge 0, n - m \equiv 0\pmod{3}\}$$ is regular. If so, then its intersection with the regular language denoted by $00^*11^*$ will be regular. Show that this intersection is equal to $$L_r = \{0^n1^m\mid n, m > 0, n - m \equiv 0\pmod{3}\}$$ and you're done. Notice that a similar construction shows that $$\{0^n1^m\mid n > k, m > j, n - m \equiv 0\pmod{3}\}$$ is also regular for any $k, j > 0$.

The same idea can be used on your second question.