Parikh's theorem

Let ${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}}$ be an alphabet. The Parikh vector of a word is defined as the function ${\textstyle p:\Sigma ^{*}\to \mathbb {N} ^{k}}$, given by[1]

$${\displaystyle p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})}$$

where ${\displaystyle |w|_{a_{i}}}$ denotes the number of occurrences of the letter ${\displaystyle a_{i}}$ in the word ${\displaystyle w}$.

A subset of ${\displaystyle \mathbb {N} ^{k}}$ is said to be linear if it is of the form

$${\displaystyle u_{0}+\mathbb {N} u_{1}+\dots +\mathbb {N} u_{m}=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}}$$

for some vectors ${\textstyle u_{0},\ldots ,u_{m}}$. A subset of ${\displaystyle \mathbb {N} ^{k}}$ is said to be semi-linear if it is a union of finitely many linear subsets.

Statement 1: Let ${\displaystyle L}$ be a context-free language. Let ${\displaystyle P(L)}$ be the set of Parikh vectors of words in ${\displaystyle L}$, that is, ${\textstyle P(L)=\{p(w)\mid w\in L\}}$. Then ${\displaystyle P(L)}$ is a semi-linear set.

Two languages are said to be commutatively equivalent if they have the same set of Parikh vectors.

Statement 2: If ${\displaystyle S}$ is any semi-linear set, the language of words whose Parikh vectors are in ${\displaystyle S}$ is commutatively equivalent to some regular language. Thus, every context-free language is commutatively equivalent to some regular language.

These two equivalent statements can be summed up by saying that the image under ${\displaystyle p}$ of context-free languages and of regular languages is the same, and it is equal to the set of semilinear sets.

A language ${\displaystyle L}$ is bounded if ${\displaystyle L\subset w_{1}^{*}\ldots w_{k}^{*}}$ for some fixed words ${\displaystyle w_{1},\ldots ,w_{k}}$. Ginsburg and Spanier [5] gave a necessary and sufficient condition, similar to Parikh's theorem, for bounded languages.

Call a linear set stratified, if in its definition for each ${\displaystyle i\geq 1}$ the vector ${\displaystyle u_{i}}$ has the property that it has at most two non-zero coordinates, and for each ${\displaystyle i,j\geq 1}$ if each of the vectors ${\displaystyle u_{i},u_{j}}$ has two non-zero coordinates, ${\displaystyle i_{1}<i_{2}}$ and ${\displaystyle j_{1}<j_{2}}$, respectively, then their order is not ${\displaystyle i_{1}<j_{1}<i_{2}<j_{2}}$. A semi-linear set is stratified if it is a union of finitely many stratified linear subsets.

The Ginsburg-Spanier theorem says that a bounded language ${\displaystyle L}$ is context-free if and only if ${\displaystyle \{(n_{1},\ldots ,n_{k})\mid w_{1}^{n_{1}}\ldots w_{k}^{n_{k}}\in L\}}$ is a stratified semi-linear set.

The theorem has multiple interpretations. It shows that a context-free language over a singleton alphabet must be a regular language and that some context-free languages can only have ambiguous grammars. Such languages are called inherently ambiguous languages. From a formal grammar perspective, this means that some ambiguous context-free grammars cannot be converted to equivalent unambiguous context-free grammars.