0
$\begingroup$

Why does {w | w has equal number of 01 and 10 substrings} not require an infinite amount of memory to “count” the number of 01 and 10 substrings?

$\endgroup$
3
  • 1
    $\begingroup$ Try some examples. You'll notice that the number of "01" substrings and the number of "10" substrings are somewhat related. $\endgroup$
    – user114966
    Apr 12 at 3:58
  • $\begingroup$ I encourage you to search thoroughly before asking, and try to solve the problem on your own. Searching this site for "01 10" turns up several relevant resources among the first few search results. $\endgroup$
    – D.W.
    Apr 12 at 4:04
  • $\begingroup$ cs.stackexchange.com/q/104695/755 $\endgroup$
    – D.W.
    Apr 12 at 4:05