Membrane

Parikh's theorem in theoretical computer science says that if we look only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding whether or not a string with given number of some terminals is accepted by a context-free grammar. It was first proved by Rohit Parikh in 1961 and republished in 1966.

Definitions and Formal Statement

Let $\mathrm{\Sigma }=\{a_1,a_2,\dots ,a_k\}$ be an alphabet. The Parikh vector of a word is defined as the function $p:{\mathrm{\Sigma }}^{*}\to {\mathbb{\mathbb{N}}}^k$, given by

$p(w)=(|w{|}_{a_1},|w{|}_{a_2},\dots ,|w{|}_{a_k})$, where $|w{|}_{a_i}$ denotes the number of occurrences of the letter $a_i$ in the word $w$.

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

$u_0+⟨u_1,\dots ,u_m⟩=\{u_0+t_1{u}_1+\dots +t_m{u}_m\mid t_1,\dots ,t_m\in \mathbb{\mathbb{N}}\}$ for some vectors $u_0,\dots ,u_m$.

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

The formal statement of Parikh's Theorem is as follows. Let $L$ be a context-free language. Let $P(L)$ be the set of Parikh vectors of words in $L$, that is, $P(L)=\{p(w)\mid w\in L\}$. Then $P(L)$ is a semi-linear set.

If $S$ is any semi-linear set, the language of words whose Parikh vectors are in $S$ is a regular language. Thus, if we consider two languages to be commutatively equivalent if they have the same set of Parikh vectors, every context-free language is commutatively equivalent to some regular language.

Significance

Parikh's theorem proves 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 an equivalent unambiguous context-free grammar.