Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.