# Question about a grammar who generates $(0+1)^*$

On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $$G$$ with the following rules: $$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$

and asks about what languages generates. In the solutions, it says that it is $$(0+1)^*$$ , but I do not see why.

I have tried to see it by induction: it is clear that $$w \in (0+1)^*$$ of length $$1$$ belongs to $$L(G)$$, so given $$n \in \Bbb{N}$$ such that $$\{ w \in (0+1)^* : |w| = n \} \subset L(G)$$, a word $$w' \in (0+1)^*, |w| = n+1$$ is of the form $$\{0w, 1w, w0, w1\}$$ with $$w \in (0+1)^*, |w|=n$$ . It is clear that $$w0$$ and $$1w$$ can be generated from the Induction hypothesis and the rules of the grammar, but I do not see how to generate $$0w$$ and $$w1$$, so any possible help would be appreciated.

We can prove this using mathematical induction. For base case, it is easy to see that $$S$$ can generate $$\varepsilon, 0, 1, 00, 11, 01, 10$$. Now we assume $$S$$ can generate any binary string on $$0$$s and $$1$$s of length up to $$k \ge 0$$ (strong induction hypothesis). We now need to prove that we can generate any binary string of length $$k+1$$.
Consider a $$k+1$$-length string, $$\omega$$. If $$\omega$$ starts with a $$1$$, we can first apply the rule $$S \rightarrow 1S$$ and then generate the remaining $$k$$ length from new $$S$$. The same holds if the string ends with a $$0$$ and we start with $$S \rightarrow S0$$. If both of this does not hold, then $$\omega$$ is of the form $$0x1$$. Note that $$x$$ is a binary string on length $$k-1$$. So in this case, we start with $$S \rightarrow 0S1$$, and then we can generate any $$k-1$$-length string $$x$$ (due to the strong induction hypothesis).