A newbie need some help in proof building. How to prove that any regular expression admits a disjunctive normal form?

Question

Prove that any regular expression admits a Disjunctive Normal Form, i.e.: R = R1 U R2 U … Rn , where neither Ri contains a union.

I would like some help with this question. If you could push me into a direction where to start, or what to read to get better at writing proofs.

Answer 1

Let $\Sigma$ be your alphabet, $a,b,c \dots \in \Sigma$. Every regular expression $R$ can be built up out of the following rules, starting at an empty string $R = 1$:

• $R = a$
• $R = R \cup S$
• $R = R S$
• $R = S^*$

where $S$ is built up using the same rules. If $S = S'\cup R'$, simply write rule 3 as $R = RS \cup RR'$ when you apply it.