patternMinor
Finding out if languages involving counting and modulo operations are regular
Viewed 0 times
countingoperationslanguagesinvolvingareregularfindingandmoduloout
Problem
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?
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?
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#30804, answer score: 3
Revisions (0)
No revisions yet.