1
$\begingroup$

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?

  • 3
    Show that the condition is equivalent to a condition that doesn't require keeping a count of anything.2012-10-22

1 Answers 1

2

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$.