Let $L = \{w \in \{a,b\}^* \mid \text{$\#_a(w)$ is odd and $\#_b(w)$ is even}\}$. Prove that $L^*$ is the set of strings where $\#_b(w)$ is even.

Question

Let \begin{align} L &= \{w \in \{a,b\}^* \mid \text{the number of $a$'s in $w$ is odd}\\ &\qquad\text{and the number of $b$'s is even}\}. \end{align}

Prove that $L^*$ is the set of strings where the number of $b$'s is even.

$\epsilon$ = empty string

let $\#_b(w)$ = number of $b$'s in string $w$

$\#_a(w)$ = number of $a$'s in string $w$

I started my proof with this :

Step Base.

Let $L^0 = \{\epsilon\}$, therefore , the number of $b$'s is even because $\#_b$(w) = $2n$ where $n = 0$.

But now, i'm confused, I don't know how to continue with the inductive step I think the induction hypothesis is to suppose that $L^n$ has an even number of $b$'s and make the proof on $L^{n+1}$.

How can I proceed with the inductive step?.

Thanks for the help.

Answer 1

Unfortunately, this is not true. Indeed, if $w = ba^2b$, then $\#_b(w)$ is even, but $w \notin L^*$.