Can every regular expression be written as sum of products?

Question

I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages. To prove this, I decided to proceed as follows:

Lemma 1: Every regular expression can be written as sum of products with star, i.e., $R = R_1 + R_2+ ... +R_n $ where each $R_i$ is a regular expression not involving any $+$.

Lemma 2: The Parikh image of a language corresponding to a regular expression that doesn't involve any $+$ is linear.

I proved the lemma 2 by induction on the structure of this specific type of regular expression. (which was easy and correct, by the way).

After proving (allegedly) these, it was easy to state that the Parikh image of the language defined by $R$ is just the union of linear sets, hence it is semi-linear.

I proved the lemma 1, again, using induction on the structure of the regular expression, but I am not sure if it is correct. Moreover, I am not sure if the Lemma 1 is even valid or not!

My proof was as follows:

1. $R = a $ where $ a \in \Sigma$ or $a=\epsilon$. This is already in the same form we required.

2. $R = R_1.R_2$ . This is also in required form.

3. $R = (R_1 + R_2).R_3$. Replace by $R_1.R_3 + R_2.R_3$.

4. $R = (R_1 + R_2)^* $ Replace by $(R_1^*.R_2^*)^*$

Do you think this proof is wrong, or even worse, the statement if wrong!

Answer 1

I think you have to be more careful in the inductive steps, but it seems you basically have the argumentation ready. According to me proper induction would be

If $R_1$ and $R_2$ can be written as sum of products, then so can $R_1\cdot R_2$, $R_1+R_2$ and $R_1^*$.

The proof could be completed as:

If $R_1$ and $R_2$ can be represented as sum of products as $R_1 = R_{11} + R_{12} + ... + R_{1n}$ and $R_2 = R_{21} + R_{22} + ... + R_{2m}$, then:

1. $R = R_1\cdot R_2$ will be equivalent to ($R_{11}\cdot R_{21} + R_{11}\cdot R_{22} + ... + R_{11}\cdot R_{2m}) + ... (R_{1n}\cdot R_{21} + R_{1n}\cdot R_{22} + ... + R_{1n}\cdot R_{2m})$, by the distributivity of concatenation over union, which is in the required form.

2. $R = R_1 + R_2$, then $R$ is already a sum of products.

3. $R = R1^{*}$ can be reduced to sum of products by repeated application of the law: $(R_1 + R_2)^* = (R_1^*\cdot R_2^*)^*$ and distributivity of concatenation over union.

Hence we can write each regular expression as sum of products.

This is called the disjunctive normal form of regular expressions.