Skip to main content
5 votes
Accepted

Why $(a+b)^* = (a^*b)^* a^*$

Consider any string $\omega$ that belongs to $(a+b)^*$. Now suppose $\omega$ contains $n$ number of $b$s. We can now partition $\omega = x_1 x_2 \dots x_n y$, where all $x_i$ are of the form $a^*b$ ...
codeR's user avatar
  • 1,390
3 votes

Why $(a+b)^* = (a^*b)^* a^*$

Every b in a string belonging to (a+b)* is preceded by 0, 1, 2 or more a's. And the last b is followed by 0, 1, 2 or more a's.
gnasher729's user avatar
  • 30.6k
2 votes
Accepted

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

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 ...
codeR's user avatar
  • 1,390
2 votes

Why $(a+b)^* = (a^*b)^* a^*$

Just as a comment, it's also possible to show this purely algebraically, using Kozen's axioms for Kleene algebra. To show that: $$\displaystyle x^*\le y$$ It is sufficient to show that: $$\...
Pseudonym's user avatar
  • 22.3k

Only top scored, non community-wiki answers of a minimum length are eligible