Inductive Proof With Regular Expression

Question

I'm trying to prove that the elements of the language $L((01+10)(01+10)^*)$ have an equal number of $0$'s and $1$'s. So far I've the base case: $R^n \to R^0 = 01 + 10$, all of which have equal number of $0$'s and $1$'s. I'm just not sure how to proceed for $R^{(n+1)}$... I've tried to simplify the expression in order to get somehow $2n$ in $10$ or $01$ but I can find a way to do it. Any suggestions?

Answer 1

Here is a possible way to solve your question. Given a word $u$, let $|u|_0$ (respectively $|u|_1$) denote the number of occurrences of $0$ (respectively $1$) in $u$. Now consider the map $f: \{0,1\}^* \to \mathbb{Z}$ defined by $$ f(u) = |u|_0 - |u|_1 $$ Observe that $u$ has an equal number of $0$'s and $1$'s if and only if $f(u) = 0$. Now here are the steps to conclude:

1. Verify that $f(01) = f(10) = 0$
2. Verify that $f(uv) = f(u) + f(v)$ and more generally, that $f(u_1 \cdots u_n) = f(u_1) + \dotsm + f(u_n)$
3. Use (2) to show that for every word $u \in \{01, 10\}^+$, $f(u) = 0$.
4. Conclude.