Show that the language of words with even sum of positions of a letter is regular

Question

Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular.

What I was thinking is to do somehow keep track of sum of positions of $a (\bmod 2)$ For that I was thinking to do like take set of states as $\{0,1\}\times \{0,1\} \times \{0,1\}$. And starting state $\{0,0,0\}$. My aim to is to keep track sum of positions of $a$ at first component. So starting from initial state, if it read consecutive $x,b$s then it will go to $(0,0,x(\bmod 2))$ then after reading $y,a$s it goes to $(xy+y(y+1)/2(\bmod 2),y(\bmod 2),x(\bmod 2)$ after reading $z,b$s it goes to $(xy+y(y+1)/2 \bmod 2),y(\bmod 2),(x+y)z+(x+y)(x+y)/2(\bmod 2)$ ... and so on. And set accepting state ${0}\times {0,1}\times {0,1}$. I believe its working but I don't understand how to define on each state.

Answer 1

If the sum of positions at which $a$s occur is even, that just means that there are an even number of $a$s in odd positions. It's straightforward to design an automaton to accept this criterion: it's a minor variant of requiring an odd number of $a$s.

Answer 2

You could do this with 4 states, interpreted as

1. Currently at an even position in the string and the sum so far is even
2. Currently at an even position in the string and the sum so far is odd
3. Currently at an odd position in the string and the sum so far is even
4. Currently at an odd position in the string and the sum so far is odd

Now it's easy enough to fill in the transitions. For example, if we're currently at an even position and the sum so far is even (i.e., in state 1), then after reading an $a$ at the position we'll find ourselves still with an even sum and will have advanced to an odd position. Formally, we have the transition $\delta(q_1, a) = q_3$. The same reasoning gives $\delta(q_1, b) = q_3$ as well. It's not hard to fill in the rest of the transitions and to determine the final states and the start state (which will depend on whether you start numbering positions at zero or one).

Cute problem, by the way.