Parikh's theorem explained

Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language.^[1] It is useful for deciding that strings with a given number of terminals are not accepted by a context-free grammar.^[2] It was first proved by Rohit Parikh in 1961^[3] and republished in 1966.^[4]

Definitions and formal statement

Let

\Sigma = \{a _{1,a} _{2,\ldots,a} _{k\}} be an alphabet. The Parikh vector of a word is defined as the function $p:\backslash Sigma^*\backslash to\backslash mathbb^k$, given by^[1] $$p(w)=(|w|\_,\; |w|\_,\; \backslash ldots,\; |w|\_)$$where |w| _{a _{i}} denotes the number of occurrences of the letter a _{i} in the word w .

A subset of

N ^{k} is said to be linear if it is of the form$$u\_0\; +\; \backslash mathbbu\_1\; +\; \backslash dots\; +\; \backslash mathbbu\_m\; =\; \backslash$$for some vectors $u\_0,\backslash ldots,u\_m$.A subset of N ^{k} is said to be semi-linear if it is a union of finitely many linear subsets.

In short, the image under

p of context-free languages and of regular languages is the same, and it is equal to the set of semilinear sets.

Two languages are said to be commutatively equivalent if they have the same set of Parikh vectors. Thus, every context-free language is commutatively equivalent to some regular language.

Proof

The second part is easy to prove.

The first part is less easy. The following proof is credited to Goldstine.^[5]

First we need a small strengthening of the pumping lemma for context-free languages:

The proof is essentially the same as the standard pumping lemma: use the pigeonhole principle to find

k copies of some nonterminal symbol A in the longest path in the shortest derivation tree.

Now we prove the first part of Parikh's theorem, making use of the above lemma.

Strengthening for bounded languages

A language

L is bounded if L\subset w ^{*\ldots} _{1} w ^{*} _{k} for some fixed words w _{1,\ldots,} w _{k} .Ginsburg and Spanier ^[6] gave a necessary and sufficient condition, similar to Parikh's theorem, for bounded languages.

Call a linear set stratified, if in its definition for each

i\ge 1 the vector u _{i} has the property that it has at most two non-zero coordinates, and for each i,j\ge 1 if each of the vectors u _{i,u} _{j} has two non-zero coordinates, i _{1<i} _{2} and j _{1<j} _{2} , respectively, then their order is not i _{1<j} _{1<i} _{2<j} _{2} .A semi-linear set is stratified if it is a union of finitely many stratified linear subsets.

Significance

The theorem has multiple interpretations. It shows that a context-free language over a singleton alphabet must be a regular language and 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 equivalent unambiguous context-free grammars.

References

1. Book: Kozen, Dexter. Automata and Computability. 1997 . Springer-Verlag. New York. 3-540-78105-6.
2. Web site: Parikh's theorem. Håkan Lindqvist. Umeå Universitet.
3. Parikh . Rohit. Rohit Jivanlal Parikh. 1961 . Language Generating Devices. Quarterly Progress Report, Research Laboratory of Electronics, MIT.
4. Parikh . Rohit. Rohit Jivanlal Parikh. 1966 . On Context-Free Languages. Journal of the Association for Computing Machinery. 13. 4. 570–581. 10.1145/321356.321364. 12263468. free.
5. Goldstine . J. . 1977-01-01 . A simplified proof of parikh's theorem . Discrete Mathematics . en . 19 . 3 . 235–239 . 10.1016/0012-365X(77)90103-0 . 0012-365X.
6. Ginsburg. Seymour. Spanier. Edwin H.. 1966 . Presburger formulas, and languages. Pacific Journal of Mathematics. 16. 2. 285–296. 10.2140/pjm.1966.16.285. free.