Let $L_{a}$ be the language $\{w \in \{a,b\}^{\ast} : |w|_{a} = |w|_{b}\}$ and let $L_{b}$ be the language $\{w \in \{a, b\}^{\ast} : $ aa or bb is substring of $w\}$. We claim that
$L_{a} \cup L_{b}$ is regular, and, for such we will prove that the regular expression
$R = (a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast} \cup (ab \cup ba)^{\ast}$ describes $L_{a} \cup L_{b}$.
Proof. We will prove that $L(R) = L_{a} \cup L_{b}$.
- Proof of $L(R) \subseteq L_{a} \cup L_{b}$.
Suppose that $w \in L(R)$, we will prove that $w \in L_{a} \cup L_{b}$ by induction on $|w|$. If $|w| = 0$, we have $w = \epsilon$, thus, $w \in L_{a}$ and therefore $w \in L_{a} \cup L_{b}$. For $|w| = 1$, this case is not possible since $a \notin L(R)$ and $b \notin L(R)$, but since, $a \notin L_{a}$ and $b \notin L_{b}$, thus for this case in particular $L(R)$ does not contradict the definitions of $L_{a}$ and of $L_{b}$.
If $|w| = 2$, then we have the following possibilities: if $w = aa$ or $w = bb$, then we have that $w \in L_{b}$, hence $w \in L_{a} \cup L_{b}$. If $w = ab$ or $w = ba$, then twe have that $w \in L_{a}$ , therefore $w \in L_{a} \cup L_{b}$.
If $|w| \geq 3$, then we have that $w = aax$, or $w = bbx$, or $w = abx$, or $w = bax$ with $x \in L(R)$. The cases that $w = aax$ or $w = bbx$, we have that $w \in L_{b}$ for any $x \in L(R)$, hence $w \in L_{a} \cup L_{b}$. The cases that $w = abx$, or $w = bax$, we have that $w \in L_{a} \cup L_{b}$ if and only if $x \in L_{a} \cup L_{b}$. But since $x \in L(R)$ and $|x| < |w|$ we have $x \in L_{a} \cup L_{b}$ by induction hypothesis. Thus, if $x \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast})$, then $x$ have substring $aa$ or substring $bb$, hence $x \in L_{b}$, and thus $w \in L_{b}$. Obviously, the cases in which $|w|_{a} = |w|_{b}$, $w$ is also in $L_{a}$. Therefore $w \in L_{a} \cup L_{b}$.
However, if $w = abx$, or $w = bax$, and $x$ does not have $aa$ and does not have $bb$ as substring, then we have that $x \in L((ab \cup ba)^{\ast})$, and by the induction hypothesis $x \in L_{a}$, thus we have $w \in L_{a}$. Therefore $w \in L_{a} \cup L_{b}$.
Therefore, given that we take a arbitrary $w$ of $L(R)$, then we can conclude that $L(R) \subseteq L_{a} \cup L_{b}$.
- Proof of $L_{a} \cup L_{b} \subseteq L(R)$.
Suppose that $w \in L_{a} \cup L_{b}$, we will prove that $w \in L(R)$ by induction on $|w|$. Since $w \in L_{a} \cup L_{b}$ then $w \in L_{a}$ or $w \in L_{b}$. If $|w| = 0$, we have that $w = \epsilon \in L_{a}$, thus $w \in L(R)$. If $|w| = 1$, this case is not possible by the same reason stated previously.
If $|w| = 2$, then we have the following possibilities: If $w \in L_{a}$, we have that $w = ab$ or $w = ba$ hence $w \in L((ab \cup ba)^{\ast}) \subseteq L(R)$. If $w \in L_{b}$, we have that $w = aa$ or $w = bb$ thus $w \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$.
If $|w| \geq 3$, then we have the following possibilities: $w = aax$, or $w = bbx$, or $w = abx$, or $w = bax$ with $x \in L_{a} \cup L_{b}$. Since $|x| < |w|$, by the inductive hypothesis we have that $x \in L(R)$ and therefore $x \in U \cup V$ with $U \subseteq L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast})$ and $V \subseteq L((ab \cup ba)^{\ast})$. The cases that $w = aax$, or $w = bbx$, we have $x \in U$, but since $aax$ and $bbx$ are in $L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$, we see that $w \in L(R)$. If $w = abx$, or $w = bax$, we have the following cases:
If $w = abx$ and $ x \in U$, then we have that $abx \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$, therefore $w \in L(R)$. \item If $w = abx$ and $ x \in V$, then we have that $abx \in L((ab \cup ba)^{\ast}) \subseteq L(R)$, therefore $w \in L(R)$.
If $w = bax$ and $ x \in U$, then we have that $bax \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$, therefore $w \in L(R)$.
If $w = bax$ and $ x \in V$, then we have that $bax \in L((ab \cup ba)^{\ast}) \subseteq L(R)$, therefore $w \in L(R)$.
Since we exhausted all possibilities, given that we take an arbitrary $w$ of $ L_{a} \cup L_{b}$, then we can conclude that $ L_{a} \cup L_{b} \subseteq L(R)$.
So, as we show that $ L(R) \subseteq L_{a} \cup L_{b}$ and $ L_{a} \cup L_{b} \subseteq L(R)$, we can conclude that $ L(R) = L_{a} \cup L_{b} $. $\square$
Is my proof okay? I am always getting confused in the inductive hypothesis, if I always using the correct number of symbols when I assume that ||≥ for some ∈ℕ.
I’m a little pressed for time and have not actually gone through the details of your argument, because I would prove regularity of $L=L_a\cup L_b$ rather differently. It’s true that this language is $L(R)$, but the fact that $L_a\cap L_b\ne\varnothing$ makes the proof a bit less straightforward than is really necessary.
Let
$$R_a=(a\cup b)^*(aa\cup bb)(a\cup b)^*\,.$$
Clearly $w\in L(R_a)$ iff there are $x,y\in\{a,b\}^*$ such that $w=xaay$ or $w=xbby$ iff $w$ has $aa$ or $bb$ as a substring iff $w\in L_a$, so $L(R_a)=L_a$.
If we can now find a regular expression $R_c$ that describes
$$L\setminus L_a=\big\{w\in\{a,b\}^*:|w|_a=|w|_b\text{ and }|w|_{aa}=|w|_{bb}=0\big\}\,,$$
we’ll be in business, because then clearly $L=L(R_a)\cup(R_c)=L(R_a\cup R_c)$. And this isn’t hard: any word that has equal numbers of $a$s and $b$s but does not contain $aa$ or $bb$ as a substring must alternate $a$s and $b$s and have even length, so it must be of the form $abab\ldots ab$ or the form $baba\ldots ba$. In other words, we can let $R_c=(ab)^*\cup(ba)^*$; it’s straightforward then to prove by induction on $|w|$ that for any $w\in\{a,b\}^*$, $w\in L\setminus L_a$ iff $w\in L(R_c)$. (I suspect that you can do that without too much trouble, but if you run into problems, just ask.)