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 the set of the context-free languages is divided to linear and semi-linear languages, today known as deterministic context-free languages and inherently ambiguous context-free languages. This also proves that the deterministic pushdown automaton is a strictly weaker device than the pushdown automaton. Deterministic context-free languages are of particular importance in compiler development because they can be parsed in linear time and most computer languages fall in this category. Parikh's theorem helps in the understanding of this set of languages, which is important for the design of mechanically generated parsers for them.