Parikh’s theorem

Let $\mathrm{\Sigma }$ be an alphabet. Fix an order on elements of $\mathrm{\Sigma }$, so that they are $a_1,\mathrm{\dots },a_n$. For each word $w$ over $\mathrm{\Sigma }$, we can form an $n$-tuple $(w_1,\mathrm{\dots },w_n)$ so that each $w_i$ is the number of occurrences of $a_i$ in $w$. The function $\mathrm{\Psi }:{\mathrm{\Sigma }}^{*}\to {\mathbb{N}}^n$ such that

$$\mathrm{\Psi }(w)=(w_1,\mathrm{\dots },w_n)$$

is called the Parikh mapping (over the alphabet $\mathrm{\Sigma }$). Here, $\mathbb{N}$ is the set of non-negative integers.

Two languages $L_1$ and $L_2$ over some $\mathrm{\Sigma }$ are called letter-equivalent if $\mathrm{\Psi }(L_1)=\mathrm{\Psi }(L_2)$.

For example, $L_1:=\{a^n{b}^n\mid n\ge 0\}$ is letter-equivalent to the $L_2:=\{{(ab)}^n\mid n\ge 0\}$, as both are mapped to the set $\{(n,n)\mid n\ge 0\}$ by $\mathrm{\Psi }$. Note that $L_1$ is context-free, while $L_2$ is regular. In fact, we have the following:

Theorem 1 (Parikh).

Every context-free language is letter-equivalent to a regular language.

Like the pumping lemma, Parikh’s theorem can be used to show that certain languages are not context-free. But in order to apply Parikh’s theorem above, one needs to know more about the structure of the set $\mathrm{\Psi }(L)$ for a given context-free language $L$.

First, note that ${\mathbb{N}}^n$ is a commutative monoid under addition. For any element $x$ and subset $S$ of ${\mathbb{N}}^n$, define $x+S$ in the obvious manner. Next, let $x_1,\mathrm{\dots },x_m$ be elements of ${\mathbb{N}}^n$. Denote

$$⟨x_1,\mathrm{\dots },x_m⟩$$

the submonoid generated by $x_1,\mathrm{\dots },x_m$.

A subset $S$ of ${\mathbb{N}}^n$ is said to be linear if it has the form

$$x_0+⟨x_1,\mathrm{\dots },x_m⟩,$$

for some $x_0,\mathrm{\dots },x_m\in {\mathbb{N}}^n$. It is not hard to see that every linear set is the image of some regular language under $\mathrm{\Psi }$. For example,

$$(1,0,0)+⟨(2,1,0),(0,3,2)⟩=\mathrm{\Psi }(\{a{(a^{2}b)}^m{(b^3{c}^2)}^n\mid m,n\ge 0\}).$$

The example can be easily generalized.

A subset of ${\mathbb{N}}^n$ is said to be semilinear if it is the union of finitely many linear sets. Since regular languages are closed under union, every semilinear set is the image of a regular language under $\mathrm{\Psi }$. As a result, Parikh’s theorem can be restated as

Theorem 2 (Theorem 1 restated).

If $L$ is context-free, then $\mathrm{\Psi }\mathit{}\mathrm{(}L\mathrm{)}$ is semilinear.

Using this theorem, one easily sees that the language $\{a^p\mid p\text{ is a prime number }\}$ is not context-free, and neither is the language

$$\{a^m{b}^n\mid \text{ either }m\text{ is prime, and }n\ge m,\text{ or }n\text{ is prime, and }m\ge n\},$$

which can not be proved by the pumping lemma in a straightforward manner.

Remarks.

• The converse of Theorem 2 above is false. For example, let $L=\{a^n{b}^n{c}^n\mid n\ge 0\}$. Then $L$ is not context-free by the pumping lemma. However, $\mathrm{\Psi }(L)=⟨(1,1,1)⟩$, which is clearly linear.

• In the literature, a lanugage $L$ such that $\mathrm{\Psi }(L)$ is semilinear is often called a slip-language. It can be shown that for a slip-language $L$ over an alphabet consisting of two symbols, the language ${\mathrm{\Psi }}^{-1}\circ \mathrm{\Psi }(L)$ is context-free.

Title	Parikh’s theorem
Canonical name	ParikhsTheorem
Date of creation	2013-03-22 18:55:49
Last modified on	2013-03-22 18:55:49
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Theorem
Classification	msc 68Q42
Classification	msc 68Q45
Defines	Parikh mapping
Defines	linear set
Defines	semilinear set
Defines	letter-equivalent
Defines	slip-language