Large DFA to regex?

Question

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language:

"the set of strings such that the number of 0’s is divisible by six, and the number of 1’s is divisible by five." over the alphabet {0, 1}.

I made a DFA for this language and it has 30 states. However, going to turn this DFA to a regular expression through state reduction is proving to be very time consuming.

What could be the better or easier way to do create a regular expression that describes that language?

Answer 1

The regular expression for this DFA is indeed going to be very large. I don't believe that it is feasible to generate it by hand, and unless the assignment requests a machine-readable version, it is going to be pretty difficult to validate.

There is a good discussion on how to algorithmically convert a DFA to a regular expression in this reference post, and I used one of the algorithms presented there to do a quick-and-dirty Python program. Using two different state elimination orders, it found regular expressions of 13,420,632 and 14,680,071 characters.

It's worth noting that the regular expressions generated automatically can usually be simplified considerably, and furthermore that the order in which you eliminate states does have an impact on the size of the regular expression produced. So it's certain there is a much shorter regular expression which would work, but I suspect that the shorter regular expressions are still pretty long.

All of this makes me wonder whether the original assignment asked for a regular grammar rather than a regular expression. The regular grammar precisely follows the DFA state transitions, so it is of manageable size: 30 non-terminals (each corresponding to a state) with a total of 60 productions (each corresponding to a transition). Writing that out by hand would be tedious but it could be generated with a much simpler program than the one needed to produce regular expressions.

Answer 2

This is near cheating, but to convert such a monster DFA to a RE by hand is cruel and unusual punishment...

Check out software, like the acclaimed JFLAP, for this. If you do use it, be sure to credit it properly.

Answer 3

Copying my approach for a similar language, only the numbers are (fortunately!) smaller. Here, the number of 0's is divisible by 2 and the number of 1's is divisible by 3. Maybe it scales for your case. The hard part is the first step, where you need to figure out all combinations of 11-sized strings with six 0's and five 1's, but you can track all possibilities with the help of a tree!

So, here it is:

Step 1: Words accepted by this language should be built up from combinations of the basic strings 00, 111, 10101, 01101, 01011, 10110 and 11010. The first two regard words where 0's and 1's are grouped together, while the rest regard words such that 0's and 1's are intertwined. However, the regular expression $$(00\mid 111\mid 10101\mid 01101\mid 01011\mid 10110 \mid 11010)^*$$ produces only part of the language. For example, it does not produce 01110.

Step 2: To produce such words, in the first basic string, we should allow groups of 1's to appear between the two 0's, and in the second we should allow groups of 0's between the 1's. Now we have $$(0(111)^*0\mid 1 (00)^* 1 (00)^* 1\mid 10101\mid 01101\mid 01011\mid 10110 \mid 11010)^*$$ This regular expression still does not completely determine the language. For example, it does not allow the word $10\color{teal}{00}101$.

Step 3: To overcome this, in the last five choices of the regular expression, for every sequence of 1's that does not start at the beginning of the string, if the sequence is followed by a 0, then we add $(111)^*$ in between. Similarly, for every sequence of 0's that does not start at the beginning of the string, if the sequence is followed by a 1, then we add $(00)^*$ in between. The reason why sequences that start at the beginning of the string are not considered is because of the outer kleene star and the first two choices. The final regular expression is: $$\left(\!\begin{aligned} & 0(111)^*0 \mid 1 (00)^* 1 (00)^* 1\mid \\ & 10 (00)^* 1(111)^*0 (00)^* 1 \mid 011(111)^*0(00)^*1\mid \\ & 01(111)^*0(00)^*11 \mid 10(00)^*11(111)^*0 \mid 110(00)^*1(111)^*0 \end{aligned}\right)^*$$ This is already a great mess for multiples of only 2 and 3, the first two primes.