Parikh's Theorem

Parikh's theorem, proved by Rohit Parikh in 1961, states that the commutative image of any context-free language is a semilinear set. In other words, if you erase the order of symbols in a context-free language and count only how many of each symbol appear, the resulting set of count vectors can be expressed as a finite union of linear sets. This is a profound structural result: it tells us that context-free languages are "almost regular" in their commutative behavior, even though their ordered structure may be arbitrarily complex.

The theorem has unexpected applications. It implies that the "slender" context-free languages — those containing at most a constant number of strings of each length — are necessarily regular. It also provides a powerful tool for proving non-context-freeness: if a language's commutative image is not semilinear, the language cannot be context-free. The language {a^n b^n c^n | n ≥ 0} is the classic example; its commutative image is the line {(n,n,n)}, which is semilinear, so Parikh's theorem does not help here. But for languages like {a^p | p prime}, the commutative image is not semilinear, and the theorem immediately establishes non-context-freeness.

Parikh's theorem connects context-free languages to additive combinatorics and the theory of Presburger arithmetic, revealing that the commutative shadow of formal language theory is richer than its ordered body.