Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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?

Asked By : Cain

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30804

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback