## Quick Reference

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*

*〉 with*

_{n}*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.

〈*N*_{1},…,*N** _{n}*〉

{Φ(*w*) | *w* ∈ *L*}

Φ(*L*_{1}) = Φ(*L*_{2})

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.

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.