# Formal languages: constructing * for a linear set

Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem).

Right now, I'm trying to construct the equivalent of *-closure for a linear set. (Once I have this, it's easy to find for semi-linear sets).

More formally:

• A linear set is a set of the form $\{ v_0 + c_1 \cdot v_1 + c_n \cdot v_n \mid c_i \in \mathbb{N}\}$. i.e. a linear combination of vectors from $\mathbb{N}^k$.
• A semi-linear set is a finite union of linear sets

For a linear set $L$, I'm trying to construct $L^*$, the semi-linear (possibly linear?) set $L^* = \{ u_1 + \ldots + u_m \mid u_i \in L, m \geq 0 \}$, i.e. the infinite sum of L with itself.

I know that this set must be semi-linear, from Parikh's theorem. It basically corresponds to the case where, if $R$ is a regular languages with a linear Parikh image $L$, then $L^*$ is the Parikh image of $R^*$. (From this I know how to build up the case where R has semi-linear Parikh image).

I'm wondering if someone can either point me to a proof that Regular Expressions are semi-linear languages that doesn't rely on Parikh's theorem for context-free languages, or can point me in the right direction for constructing $L^*$ myself.

• Note: I realize this probably falls more under pure Math than computer science, but I thought it would fit here, since it's easiest to explain in the context of regular languages. – jmite Jul 19 '15 at 21:25
• "Regular Expressions are semi-linear languages" -- do you mean the language of regular expressions, or the class of all regular languages? – Raphael Jul 20 '15 at 6:05

Hint. It suffices to observe that if $L = \{ v_0 + c_1v_1 + c_nv_n \mid c_1, \dotsm, c_n \in \mathbb{N}\}$, then $L^* = \{ c_0v_0 + c_1v_1 + c_n v_n \mid c_0, \dotsm, c_n \in \mathbb{N}\}$.