If true, prove (01+0)*0 = 0(10+0)*, else provide a counter example.

242 Views Asked by At

Just by trying out a few examples, two regular expressions seem to be equivalent.

Here's my attempt at the proof.

We'll prove that $(01+0)^n0 = 0(10+0)^n \textrm{ }\forall n \in \mathbb{N}$.

$$(01+0)^{n+1}0 \\= (01+0)(01+0)^n0\\=(01+0)0(10+0)^n \textrm{ (by induction)}\\=(010+00)(10+0)^n\\=0(10+0)(10+0)^n\\=0(10+0)^{n+1}$$