5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jmite Jul 19 '15 at 21:25
  • $\begingroup$ "Regular Expressions are semi-linear languages" -- do you mean the language of regular expressions, or the class of all regular languages? $\endgroup$ – Raphael Jul 20 '15 at 6:05
5
$\begingroup$

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}\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.