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