# Parikhs theorem

**Parikh's theorem** A theorem in formal language theory that concerns the nature of context-free languages when order of letters is disregarded.

Let the alphabet Σ be the set {*a*_{1},…,*a _{n}*}. The

*letter distribution*, φ(

*w*), of a Σ-word

*w*is the

*n*-tuple 〈

*N*

_{1},…,

*N*〉

_{n}with

*N*the number of occurrences of

_{i}*a*in

_{i}*w*. The

*Parikh image*, φ(

*L*), of a Σ-language

*L*is {φ(

*w*) |

*w*∈

*L*}

i.e. the set of all letter-distributions of words in

*L*.

*L*

_{1}and

*L*

_{2}are

*letter-equivalent*if φ(

*L*

_{1}) = φ(

*L*

_{2})

Letter distributions may be added component-wise as vectors. This leads to the following: a set

*S*of letter distributions is

*linear*if, for some distributions

*d*and

*d*

_{1},…,

*d*,

_{k}*S*is the set of all sums formed from

*d*and multiples of

*d*.

_{i}*S*is

*semilinear*if it is a finite union of linear sets.

Parikh's theorem now states that if

*L*is context-free φ(

*L*) is semilinear. It can also be shown that φ(

*L*) is semilinear if and only if

*L*is letter-equivalent to a regular language. Hence any context-free language is letter-equivalent to a regular language – although not all such languages are context-free.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**Parikhs theorem**