0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could the down-voters let a comment to explain their down vote? $\endgroup$ – J.-E. Pin Aug 20 '14 at 21:25
  • 1
    $\begingroup$ Probably because it seems to fit a kind of question that is generally disliked (cf here and here). $\endgroup$ – Raphael Aug 21 '14 at 5:52
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's noteworthy that we use that adding numbers $\mod 2$ only needs the last bits; if that was not the case, FA couldn't do it. Thanks, mathematics! $\endgroup$ – Raphael Aug 21 '14 at 5:53

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.