# Give a DFSA that accepts $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$ using as few states as possible

Let $$L_1$$ be the language over alphabet $$\{0, 1\}$$ defined by $$L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$$.

Using as few states as possible, give a DFSA that accepts $$L_1$$.

Also give an appropriate state invariant for your DFSA.

I have a regex for it and that is $$1^*(00^*11^*00^*11^*00^*11^*)1^*$$.

An example of accepted strings are: 100111010001. Example of a rejected string is 01010101, since |01010101| $$= 4 \mod 3 = 1 \neq 0$$.

How would I draw it? Also do I come up with state invariant first or draw the dfsa first? I drew the dfsa first right now

100111010001 - gets accepted. However 01010101 also gets accepted when it should be rejected. Not sure how to limit it to just mod 3

Edit:

I believe this works. (I cant use regexes in state invariants)

$$q_0$$: $$x$$ must contain only $$1$$'s

$$q_1$$: $$x$$ contains 1's before any 0's and ends with a 0

..

not sure how to write the state invariant for this case

Hint, a correct regular expression is $$1^*(00^*11^*00^*11^*00^*11^*)^*0^*$$.
There are 6 states, where $$q_{0,1}$$ is the initial state. Both $$q_{0,1}$$ and $$q_{0,0}$$ are accepting states.
$$q_{0,1}$$: the number of 01s is a multiple of 3 and it ends with 1. Or empty word.
$$q_{0,0}$$: the number of 01s is a multiple of 3 and it ends with 0.
$$q_{1,1}$$: the number of 01s is 1 plus a multiple of 3 and it ends with 1.
$$q_{1,0}$$: the number of 01s is 1 plus a multiple of 3 and it ends with 0.
$$q_{2,1}$$: the number of 01s is 2 plus a multiple of 3 and it ends with 1.
$$q_{2,0}$$: the number of 01s is 2 plus a multiple of 3 and it ends with 0.