Parikh's Theorem

Fabian Lehr 📧

June 26, 2025

Abstract

In formal language theory, the Parikh image of a language $L$ is the set of multisets of the words in $L$: the order of letters in a word becomes irrelevant, only the number of occurrences is relevant. Parikh's Theorem states that the Parikh image of a context-free language is the same as the Parikh image of some regular language. This formalization closely follows Pilling's proof: It describes a context-free language as a minimal solution to a system of equations induced by a context free grammar for this language. Then it is shown that there exists a minimal solution to this system which is regular, such that the regular solution and the context-free language have the same Parikh image.

License

BSD License

Topics

Related publications

  • Pilling, D. L. (1973). Commutative Regular Equations and Parikh’s Theorem. Journal of the London Mathematical Society, s2-6(4), 663–666. Portico. https://doi.org/10.1112/jlms/s2-6.4.663
  • https://en.wikipedia.org/wiki/Parikh%27s_theorem

Session Parikh