How would you draw a state diagram for a DFA over the alphabet $\{0,1\}$ that recognizes the following language:
$$\{w=w_1w_2\ldots w_n\in\Sigma^*\mid(w_1-w_2+\ldots+(-1)^{k-1}w_k\bmod4=0\text{ for }k\geq0\text{ and }w_i\in\{0,1\}\}$$
I don't really know where to start. I am confused as to what that $\bmod 4$ is there for. Also, What would be the regular expression that would describe this language? Thanks for the help.
I'll give you the DFA, you can figure out why it works
$$Q=\{1,-1\}\times\{0,1,2,3\}$$$$\Sigma=\{0,1\}$$$$\delta((a,b),s)=(-a,b+as\bmod4)$$$$q_0=(1,0)$$$$F=\{1,-1\}\times\{0\}$$
The words in this language are those where when you take the alternating sum of the bits, you get something that is divisible by $4$ (hence the $\equiv 0 \bmod 4$ part). So for example $111010101$ is in the language since $1-1+1-0+1-0+1-0+1 = 4$ is divisible by $4$.
Intuitively, as you proceed through the string, if you keep track of the alternating sign ($+$ or $-$) and the remainder modulo $4$, then if you end up with $0$ then your string is valid.
So let the states be the remainders modulo $4$ modified by a $+$ or $-$ symbol—that is: $$\begin{array}{cc} 0^+ & 0^- \\ 1^+ & 1^- \\ 2^+ & 2^- \\ 3^+ & 3^- \end{array}$$ The start state is $0^+$ and the accept states are $0^+$ and $0^-$.
Each bit flips the sign and adds or subtracts $0$ or $1$ modulo $4$—specifically, if you're in state $r^{\pm}$, then $w$ sends you to $(r \pm w \bmod 4)^{\mp}$, where the $\pm$ sign matches that of the original state $r^{\pm}$ and $\mp$ is the opposite sign. For example $q(3^-, 1) = 2^+$ and $q(1^+, 0) = 1^-$.
See if you can make this formal, and figure out the details of the regular expression.
