Parikh's theorem

Let $\backslash Sigma=\backslash \{a\_1,a\_2,\backslash ldots,a\_k\backslash \}$ be an alphabet. The Parikh vector of a word is defined as the function $p:\backslash Sigma^*\backslash to\backslash mathbb\{N\}^k$, given by

$$p(w)=(|w|\_\{a\_1\},\; |w|\_\{a\_2\},\; \backslash ldots,\; |w|\_\{a\_k\})$$

where $|w|\_\{a\_i\}$ denotes the number of occurrences of the symbol $a\_i$ in the word $w$.

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

$$u\_0\; +\; \backslash mathbb\{N\}u\_1\; +\; \backslash dots\; +\; \backslash mathbb\{N\}u\_m\; =\; \backslash \{u\_0+t\_1u\_1+\backslash dots+t\_mu\_m\; \backslash mid\; t\_1,\backslash ldots,t\_m\backslash in\backslash mathbb\{N\}\backslash \}$$

for some vectors $u\_0,\backslash ldots,u\_m$.

A subset of $\backslash mathbb\{N\}^k$ is said to be semi-linear if it is a union of finitely many linear subsets.

{{Math theorem|name=Theorem|note=|math_statement=

Let $L$ be a context-free language or a regular language, let $P(L)$ be the set of Parikh vectors of words in $L$, that is, $P(L)\; =\; \backslash \{p(w)\; \backslash mid\; w\; \backslash in\; L\backslash \}$. Then $P(L)$ is a semi-linear set.

If $S$ is any semi-linear set, then there exists a regular language (which a fortiori is context-free) whose Parikh vectors is $S$.

}}

In short, the image under $p$ of context-free languages and of regular languages is the same, and it is equal to the set of semilinear sets.

Two languages are said to be commutatively equivalent if they have the same set of Parikh vectors. Thus, every context-free language is commutatively equivalent to some regular language.

The second part is easy to prove.

{{Math proof|title=Proof|proof=

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

$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 $S\; =\; \backslash \{u\_0+t\_1u\_1+\backslash dots+t\_mu\_m\; \backslash mid\; t\_1,\backslash ldots,t\_m\backslash in\backslash mathbb\{N\}\backslash \}$, then it is the set of Parikh vectors of $\backslash \{z\_0\backslash \}\; \backslash cdot\; (\backslash cup\_\{i=1\}^m\; \backslash \{z\_i\backslash \})^*$, where each $z\_i$ has Parikh vector $u\_i$.

}}

The first part is less easy. The following proof is credited to Goldstine.{{Cite journal |last=Goldstine |first=J. |date=1977-01-01 |title=A simplified proof of parikh's theorem |url=https://dx.doi.org/10.1016/0012-365X%2877%2990103-0 |journal=Discrete Mathematics |language=en |volume=19 |issue=3 |pages=235–239 |doi=10.1016/0012-365X(77)90103-0 |issn=0012-365X}}

First we need a small strengthening of the pumping lemma for context-free languages:

{{Math theorem

| name = Lemma

| note =

| math_statement = If $L$ is generated by a Chomsky normal form grammar, then $\backslash exists\; N\; \backslash geq\; 1$, such that the following is true.

For any $k\; \backslash geq\; 1$, and for any $w\; \backslash in\; L$ with $|w|\; \backslash geq\; N^k$, given a derivation $S\; \backslash Rightarrow^*\; uAv$ of $w$ from the axiom $S$, we can split $w$ into segments $w\; =\; ux\_1\backslash cdots\; x\_kzy\_k\backslash cdots\; y\_1v$, and pick a nonterminal symbol $A$, such that we have:

$$|x\_iy\_i|\backslash geq\; 1$$ for all $i$, and $|x\_1\backslash cdots\; x\_kzy\_k\backslash cdots\; y\_1|\; \backslash leq\; N^k$

and the derivation $S\; \backslash Rightarrow^*\; uAv$ can be split in the following (with the same parse tree, in particular using precisely the same nonterminals):

$$S\; \backslash Rightarrow^*\; uAv\backslash quad\; \backslash forall\; i,\; A\; \backslash Rightarrow^*\; x\_iAy\_i\; A\; \backslash Rightarrow^*\; z\backslash quad$$

}}

The proof is essentially the same as the standard pumping lemma: use the pigeonhole principle to find $k$ copies of some nonterminal symbol $A$ in the longest path in the shortest derivation tree.

Now we prove the first part of Parikh's theorem, making use of the above lemma.

{{Math proof|title=Proof|proof=

First, construct a Chomsky normal form grammar for $L$.

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

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

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

$$G\; =\; \backslash \{xy:\; 1\; \backslash leq\; |xy|\; \backslash leq\; N^k\; \backslash text\{\; and\; there\; exists\; \}\; A\backslash in\; U\; \backslash text\{\; such\; that\; \}\; A\; \backslash Rightarrow^*\_U\; xAy\backslash \}$$

To prove $p(L\_U)\; \backslash subset\; p(F\backslash cdot\; G^*)$, we induct on the length of $w\backslash in\; L\_U$.

: If , then $w\; \backslash in\; F$, so $p(w)\; \backslash in\; p(F\backslash cdot\; G^*)$. Otherwise, since $w\; \backslash in\; L\_U$, there is a derivation of $w$ using precisely the elements of $U$. By the strengthened pumping lemma, this derivation can be rewritten to be of the form

$$S$$

\underset{d_0}{\stackrel{*}{\Rightarrow}} u A v

\underset{d_1}{\stackrel{*}{\Rightarrow}} u x_1 A y_1 v

\underset{d_2}{\stackrel{*}{\Rightarrow}} \cdots

\underset{d_{k}}{\stackrel{*}{\Rightarrow}} u x_1 \cdots x_k A y_k \cdots y_1 v

\underset{d_{k+1}}{\stackrel{*}{\Rightarrow}} u x_1 \cdots x_k z y_k \cdots y_1 v

: where $A\backslash in\; U$, $1\; \backslash leq\; |x\_iy\_i|$, and $|x\_1\; \backslash cdots\; x\_k\; z\; y\_k\; \backslash cdots\; y\_1|\; \backslash leq\; N^k$.

: Since there are only $k-1$ elements in $U\backslash setminus\; \backslash \{A\backslash \}$, but there are $k$ sub-derivations $d\_1,\; ...,\; d\_k$ in the middle, picking one witnessing subderivation to use each of the nonterminals in $U\backslash setminus\; \backslash \{A\backslash \}$, we may delete one sub-derivation $d\_i$ and obtain a shorter $w\text{'}$ that still uses all the nonterminals of $U$, i.e., which is still in $L\_U$, with

$$p(w)\; =\; p(uzv)\; +\; p(x\_1y\_1)\; +\; \backslash cdots\; +\; p(x\_ky\_k)\; =\; p(w\text{'})\; +\; p(x\_iy\_i)$$

: By induction, $p(w\text{'})\; \backslash in\; p(F\backslash cdot\; G^*)$, and by construction, $x\_iy\_i\backslash in\; G$, so $p(w)\backslash in\; p(F\backslash cdot\; G^*)$.

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

: If no factor from $G$ is needed, then $w\; \backslash in\; F\; \backslash subset\; L\_U$.

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

: By induction, $p(w\text{'})\; =\; p(w$) for some $w$\in L_U. By construction of $G$, there exists some $A\backslash in\; U$ such that $A\backslash Rightarrow^*\_U\; xAy$.

: By construction of $L\_U$, the symbol $A$ appears in a derivation of $w$ using exactly all of $U$. Then we can interpolate $A\backslash Rightarrow^*\_U\; xAy$ into that derivation to obtain some $w$'\in L_U such that

$$p(w$$') = p(w) + p(xy) = p(w') + p(xy) = p(w)

}}

A language $L$ is bounded if $L\backslash subset\; w\_1^*\backslash ldots\; w\_k^*$ for some fixed words $w\_1,\backslash ldots,\; w\_k$.

Ginsburg and Spanier {{cite journal |last1=Ginsburg|first1=Seymour|last2=Spanier|first2=Edwin H.|year=1966 |title=Presburger formulas, and languages|journal=Pacific Journal of Mathematics|volume=16|issue=2|pages=285–296|doi=10.2140/pjm.1966.16.285|url=https://projecteuclid.org/euclid.pjm/1102994974|doi-access=free}}

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 $i\backslash ge\; 1$ the vector $u\_i$ has the property that it has at most two non-zero coordinates, and for each $i,j\backslash ge\; 1$ if each of the vectors $u\_i,u\_j$ has two non-zero coordinates, not

A semi-linear set is stratified if it is a union of finitely many stratified linear subsets.

{{Math theorem|name=Ginsburg-Spanier|note=|math_statement=

A bounded language $L$ is context-free if and only if $\backslash \{(n\_1,\backslash ldots,n\_k)\backslash mid\; w\_1^\{n\_1\}\backslash ldots\; w\_k^\{n\_k\}\backslash in\; L\backslash \}$ 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{{explain|reason=why exactly?|date=April 2017}}. 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.

Category:Formal languages