Parikh's theorem

Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding whether or not a string with a given number of some terminals is accepted by a context-free grammar. It was first proved by Rohit Parikh in 1961 and republished in 1966.

Let ${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}}$ be an alphabet. The Parikh vector of a word is defined as the function ${\displaystyle p:\Sigma ^{*}\to \mathbb {N} ^{k}}$, given by

...
Wikipedia