How to write the set builder notation for this DFA.

783 Views Asked by At

Please see the image for the DFA

enter image description here

So far I have the following notation but am unsure how to convert the text part into a more mathematical notation. I'm also not sure if I am allowed to use the star closure of the alphabet $\{0,1\}^*$

$w \:\varepsilon \:\{0,1\}^* :\:$ number of 1s is even, number of 0s congruent with 1(mod3)

&&

$w \:\varepsilon \:\{0,1\}^* :\:$ number of 1s is odd, number of 0s congruent with 2(mod3)

Thank you

1

There are 1 best solutions below

8
On BEST ANSWER

Let's look first at the structure of the cycles in this DFA. You can get from any state back to itself with two 1s or three 0s, but you can also break out of those cycles into larger cycles. Because of the symmetry of the cycles between states, any input with the number of 0s being a multiple of three and the number of 1s being a multiple of two leads you back to the same state again.

With that information we can look now at all inputs that land us on accepting state q1. From starting state q5, a single 0 gets us to q1, and because of the symmetry mentioned above, so will any string containing an even number of 1s and any number of 0s such that the number is congruent to 1 (mod 3).

Running through similar reasoning, inputs leading to accepting state q3 will be any input containing an odd number of 1s, and a number of 0s congruent to 2 (mod 3).

From there as long as you don't need to write the set builder notation with a regular expression it should be straightforward.