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
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