Proving two languages are equal

Question

Q: Show that $\{a,b\}^* = \{a\}^*(\{b\}\{a\}^*)^*$.

I am aware of the fact that both sides are sets, infinite sets actually. So for example showing that both sides are subsets of each other would be a proof. But I don't know how to proceed if I choose to do that way. Should I use mathematical induction instead on the string length? It's my first time seeing something like this so I really am lost and open to any help.

Answer 1

HINT: Since $\{a,b\}^*$ is the set of all finite strings over the alphabet $\{a,b\}$, and every member of $\{a\}^*(\{b\}\{a\}^*)^*$ is clearly a string over that alphabet, the inclusion

$$\{a\}^*(\{b\}\{a\}^*)^*\subseteq\{a,b\}^*$$

is clear. Thus, you really just have to show that every string over $\{a,b\}$ is in $\{a\}^*(\{b\}\{a\}^*)^*$.

Induction on the length of the string is a reasonable idea, but you may find it easier to proceed by induction on the number of $b$s in the string. If there are none, then the string is clearly in $\{a\}^*$, which is easily seen to be a subset of $\{a\}^*(\{b\}\{a\}^*)^*$. For the induction step, suppose that every string in $\{a,b\}^*$ with $n$ $b$s is in $\{a\}^*(\{b\}\{a\}^*)^*$, let $\sigma\in\{a,b\}^*$ have $n+1$ $b$s, and show that $\sigma\in\{a\}^*(\{b\}\{a\}^*)^*$. To do this, you’ll want to split $\sigma$ appropriately into two substrings.

Answer 2

Brian's answer of using induction on the number of $b$'s is the prefered way, but just to give another solution (which in this simple case might be a little bit overkill, but at least gives a different perspective).

Notice that both languages are regular and as already said it is easy to see that $\{a,b\}^{\ast}$ describes the set of all string with $a$ and $b$'s. Now construct a fsm for the second expression which directly matches its form:

Now remember how to minimize an automaton: recognize equivalent states and merge them. Two states are equivalent if you start from them, they give the same languages. First notice that without altering the accepted language you can add a second $a$ to the first arc from $q_0$ to $q_1$, and then by symmetry you see that they have to describe the same language. Hence you can collapse them into a single state, and the resulting automaton which just consists of a single (final) state and a loop for $a$ and $b$ obviously accepts every string.

EDIT: $q_1$ has to be final too, fixed that.

Answer 3

Here is another possible solution. It is based on the fact that any word of $\{a,b\}^*$ can be uniquely written in the form $a^{n_0}ba^{n_1}ba^{n_2} \dotsm ba^{n_k}$ where $k \geqslant 0$ and $n_0, \dots, n_k \geqslant 0$. Note that $n_0, \dots, n_k$ can be equal to $0$ and $a^0$ is the empty word. Thus for instance $abbaaaba = a^{\color{red}1}ba^{\color{red}0}ba^{\color{red}3}ba^{\color{red}1}$.

Now $a^{n_0}ba^{n_1}ba^{n_2} \dotsm ba^{n_k} = (a^{n_0})(ba^{n_1})(ba^{n_2}) \dotsm (ba^{n_k})$ and since $a^{n_0} \in a^*$ and $ba^{n_1}, ba^{n_2}, \dots, ba^{n_k} \in ba^*$, one gets $a^{n_0}ba^{n_1}ba^{n_2} \dotsm ba^{n_k} \in a^*(ba^*)^*$ as required.