Parikh's theorem

Definitions and formal statement

Let Σ = { a 1 , a 2 , … , a k } be an alphabet. The Parikh vector of a word is defined as the function p : Σ ∗ → N k , given by

p ( w ) = ( | w | a 1 , | w | a 2 , … , | w | a k ) , 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 + ⟨ u 1 , … , u m ⟩ = { u 0 + t 1 u 1 + … + t m u m ∣ t 1 , … , t m ∈ N } for some vectors u 0 , … , u m .

A subset of N k is said to be semi-linear if it is a union of finitely many linear subsets.

The formal statement of Parikh's theorem is as follows. Let L be a context-free language. Let P ( L ) be the set of Parikh vectors of words in L , that is, P ( L ) = { p ( w ) ∣ w ∈ L } . Then P ( L ) is a semi-linear set.

Two languages are said to be commutatively equivalent if they have the same set of Parikh vectors. If S is any semi-linear set, the language of words whose Parikh vectors are in S is commutatively equivalent to some regular language. Thus, every context-free language is commutatively equivalent to some regular language.

Significance

Parikh's theorem proves 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.