Parikh's theorem

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

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

$p(w)=(\#a_{1}(w),\#a_{2}(w),\ldots ,\#a_{k}(w))$, where $\#a_{i}(w)$ gives the number of occurrences of the letter $a_{i}$ in the word $w$.

Further, for a language $L$, $p(L)=\{p(w)|w\in L\}$

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

$u_{0}+\langle u_{1},\ldots ,u_{m}\rangle =\{u_{0}+a_{1}u_{1}+\ldots +a_{m}u_{m}|a_{1},\ldots ,a_{m}\in \mathbb {N} \}$ for some vectors $u_{0},\ldots ,u_{m}$.

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

Significance

Parikh's theorem proves that some context-free languages can only have ambiguous grammars. Such languages are called inherently ambiguous. From a formal grammar perspective this means that some ambiguous context-free grammars cannot be converted to an eqivalent unambiguous context-free grammar.