1
$\begingroup$

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

enter image description here

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

Edit:

enter image description here

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.