A Generalisation of Parikh's Theorem in Formal Language Theory
We show that when a family of languages F has a few appropriate closure-properties, all languages algebraic over F are still equivalent to languages in F when occurrences of symbols are permuted. At the same time, the methods used imply a new and simple algebraic proof of Parikh’s original theorem, directly transforming an arbitrary context-free grammar into a letter-equivalent regular grammar. Further applications are discussed.