Parikh's theorem

Given semi-linear set ${\displaystyle S}$, to construct a regular language whose set of Parikh vectors is ${\displaystyle S}$.

${\displaystyle S}$ is a union of 0 or more linear sets. Since the empty language is regular, and union of regular languages is regular, it suffices to prove that any linear set is the set of Parikh vectors of a regular language.

Let ${\displaystyle S=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}}$, then it is the set of Parikh vectors of ${\displaystyle \{z_{0}\}\cdot (\cup _{i=1}^{m}\{z_{i}\})^{*}}$, where each ${\displaystyle z_{i}}$ has Parikh vector ${\displaystyle u_{i}}$.

First, construct a Chomsky normal form grammar for ${\displaystyle L}$.

For each finite nonempty subset of nonterminals ${\displaystyle U}$, define ${\displaystyle L_{U}}$ to be the set of sentences in ${\displaystyle L}$ such that there exists a derivation that uses every nonterminal in ${\displaystyle U}$, no more and no less. It is clear that ${\displaystyle L=\cup _{U}L_{U}}$, so it suffices to prove that each ${\displaystyle p(L_{U})}$ is a semilinear set.

Now fix some ${\displaystyle U}$, and let ${\displaystyle k=|U|}$. We construct two finite sets ${\displaystyle F,G}$, such that ${\displaystyle p(L_{U})=p(F\cdot G^{*})}$, which is obviously semilinear.

For notational clarity, write ${\displaystyle \Rightarrow _{U}^{*}}$ to mean "there exists a derivation using no more (but possibly less) than nonterminals in ${\displaystyle U}$. With that, we define ${\displaystyle F,G}$ as follows:

$${\displaystyle F=\{w\in L_{U}:|w|<N^{k}\}}$$ $${\displaystyle G=\{xy:1\leq |xy|\leq N^{k}{\text{ and there exists }}A\in U{\text{ such that }}A\Rightarrow _{U}^{*}xAy\}}$$

To prove ${\displaystyle p(L_{U})\subset p(F\cdot G^{*})}$, we induct on the length of ${\displaystyle w\in L_{U}}$.

If ${\displaystyle |w|<N^{k}}$, then ${\displaystyle w\in F}$, so ${\displaystyle p(w)\in p(F\cdot G^{*})}$. Otherwise, by the strengthened pumping lemma, there exists a derivation of ${\displaystyle w}$ using precisely the elements of ${\displaystyle U}$, and is of the form

$${\displaystyle S{\underset {d_{0}}{\stackrel {*}{\Rightarrow }}}uAv{\underset {d_{1}}{\stackrel {*}{\Rightarrow }}}ux_{1}Ay_{1}v{\underset {d_{2}}{\stackrel {*}{\Rightarrow }}}\cdots {\underset {d_{k}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}Ay_{k}\cdots y_{1}v{\underset {d_{k+1}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v}$$

where ${\displaystyle A\in U}$, ${\displaystyle 1\leq |x_{i}y_{i}|}$, and ${\displaystyle |x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}}$.

Since there are only ${\displaystyle k-1}$ elements in ${\displaystyle U\setminus \{A\}}$, but there are ${\displaystyle k}$ sub-derivations ${\displaystyle d_{1},...,d_{k}}$ in the middle, we may delete one sub-derivation ${\displaystyle d_{i}}$, and obtain a shorter ${\displaystyle w'}$ that is still in ${\displaystyle L_{U}}$, with

$${\displaystyle p(w)=p(uzv)+p(x_{1}y_{1})+\cdots +p(x_{k}y_{k})=p(w')+p(x_{i}y_{i})}$$

By induction, ${\displaystyle p(w')\in p(F\cdot G^{*})}$, and by construction, ${\displaystyle x_{i}y_{i}\in G}$, so ${\displaystyle p(w)\in p(F\cdot G^{*})}$.

To prove ${\displaystyle p(L_{U})\supset p(F\cdot G^{*})}$, consider an element ${\displaystyle w\in F\cdot G^{*}}$. We need to show that ${\displaystyle p(w)\in p(L_{U})}$. We induct on the minimal number of factors from ${\displaystyle G}$ that is needed to identify ${\displaystyle w}$ as an element of ${\displaystyle F\cdot G^{*}}$.

If no factor from ${\displaystyle G}$ is needed, then ${\displaystyle w\in F\subset L_{U}}$.

Otherwise, ${\displaystyle w=w'xy}$ for some ${\displaystyle w'\in F\cdot G^{*}}$ and ${\displaystyle xy\in G}$, where ${\displaystyle w'}$ requires less factors from ${\displaystyle G}$ than ${\displaystyle w}$.

By induction, ${\displaystyle p(w')=p(w'')}$ for some ${\displaystyle w''\in L_{U}}$. By construction of ${\displaystyle G}$, there exists some ${\displaystyle A\in U}$ such that ${\displaystyle A\Rightarrow _{U}^{*}xAy}$.

By construction of ${\displaystyle L_{U}}$, the symbol ${\displaystyle A}$ appears in a derivation of ${\displaystyle w''}$ using exactly all of ${\displaystyle U}$. Then we can interpolate ${\displaystyle A\Rightarrow _{U}^{*}xAy}$ into that derivation to obtain some ${\displaystyle w'''\in L_{U}}$ such that

$${\displaystyle p(w''')=p(w'')+p(xy)=p(w')+p(xy)=p(w)}$$