# Why is the languge of same occurences of ab and ba regular?

Let the language $L = \{ s~|~s\text{ has the same number of "ab"s as "ba"s.} \}$ for the alphabet $\Sigma = \{ a, b \}$. Apparently, $L$ is regular. Why? Wouldn't a machine that recognizes $L$ have to keep a count of either substring?

-
Show that the condition is equivalent to a condition that doesn't require keeping a count of anything. –  Qiaochu Yuan Oct 22 '12 at 17:45

HINT: Let $w=x_1x_2\dots x_n\in\{a,b\}^*$. Initialize $k$ to $0$, and set $i=1$. Now scan $w$ from left to right, setting $i=1,2,\dots,n-1$ and modifying $k$ according to the following algorithm:
If $x_i=a$ and $x_{i+1}=b$, increase $k$ by $1$; if $x_i=b$ and $x_{i+1}=a$, decrease $k$ by $1$; and if $x_i=x_{i+1}$, leave $k$ unchanged.
1. What are the possible values of $k$?
2. How can you use $k$ to decide whether $w\in L$?
3. Now design a DFA that uses $k$ to decide whether $w\in L$.