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.
On
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.
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\}$$