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 a string with given number of some terminals is accepted by a context-free grammar.. It was first proved by Rohit Parikh 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 integers $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.

Statement

Parikh's theorem says that for any context-free language $A$, the set $p(A)$ is semi-linear.

Proof

Let $G=(N,\Sigma ,P,S)$ be a context free grammar in the Chomsky normal form. Let $s,t,\ldots$denote parse trees of $G$ with non-terminal at the root, non-terminals labeling internal nodes and terminals or non-terminals labeling leaves. A root is defined as the non-terminal at the root of the tree $s$, yield is the string of terminals and non-terminals at the leaves of $s$ reading left to right.