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?
Why is the languge of same occurences of ab and ba regular?
1
$\begingroup$
regular-language
-
3Show that the condition is equivalent to a condition that doesn't require keeping a count of anything. – 2012-10-22