Yet another proof of Parikh's Theorem

Abstract

Parikh's Theorem says that the Parikh image of a context-free language is semilinear. We give a short proof of Parikh's Theorem using the formulation of Verma, Seidl, and Schwentick in terms of Presburger arithmetic. The proof relies on an Eulerian property of derivation trees of context-free languages and was inspired by Hierholzer's algorithm; it does not use the Chomsky normal form.