Take the 2-minute tour ×
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.

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|improve this question
3  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.