What's the recursive definition of the heavy binary strings?

Question

Given $Σ = \{0, 1\}$ and $w ∈ Σ^*$. The binary string $w$ is called heavy if (the number of $1$ of $w$) - (the number of $0$ of $w$) = $1$. For example, the strings $011$, $100011110$ are heavy, while the strings $0101$, $1100$, $1100100$, $1111111$ are not.

What's the recursive definition of the heavy binary strings?

Answer 1

If $H$ is the set of these heavy strings, then define the basis step as $1\in H$.

Now if $x, y$ are two strings in $H$, then the concatenations $xy$ or $yx$ will have two more $1$'s than the $0$'s. So we need to add one more zero in the string $xy$ for it to be a member of $H$. So the recursive step can be given as: if $x, y\in H$ then $0xy, x0y, xy0\in H.$

Answer 2

Peter Linz give a solution in his book https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241, ch1.2.

First he builds a language for the equal occurrences of 1's and 0's.

( I will note the 1's and 0's with a and b - for example 10101 becomes ababa. Instead of $\lambda$ I use 1. )

L = 1 + L.L + a.L.b + b.L.a and he proves that every required word is in L.

In the second step, H = a.L + L.H

For the proposed recurrence H = a + b.H.H + H.b.H + H.H.b, one must prove that any heavy word is covered. For this we may use a counter that subtracts or add 1 for each b or a. For example aaabb will have a counter sequence 012321. The last digit refers to the number of extra a's. I will note this like $^0a^1a^2a^3b^2b^1$ . The heavy words have a finishing digit of 1 in their counter sequence.

If the word w starts with b, we remove the first b and the remaining counter sequence will be 0....1....2, necessarily passing somewhere by 1, and revealing w is b.H.H word. The same is the approach if the word finishes in b.

If the heavy word starts and ends by a, the counter technique show there is a b in the middle because we have to decrease from 1 to 0: $^0a^1.....^{15}b^{14}.......^0a^1$

then another b must be to the right, and another one, till we get

$^0a^1.....^{1}b^{0}.......^0a^1$ and a H.b.H word.

other case is one like $^0a^1.....^{-14}b^{-15}.......^0a^1$ there has to be a b to the left, and another one etc. till

$^0a^1.....^{1}b^{0}.......^0a^1$ we get a H.b.H word.