A Post canonical system, also known as a Post production system, as created by Emil Post, is a string-manipulation system that starts with finitely-many strings and repeatedly transforms them by applying a finite set j of specified rules of a certain form, thus generating a formal language.
In many contexts, each production rule has only one antecedent, thus taking the simpler form The formal language generated by a Post canonical system is the set whose elements are the initial words together with all words obtainable from them by repeated application of the production rules.
Such sets are recursively enumerable languages and every recursively enumerable language is the restriction of some such set to a sub-alphabet of A.
A Post canonical system is said to be in normal form if it has only one initial word and every production rule is of the simple form Post 1943 proved the remarkable Normal-form Theorem, which applies to the most-general type of Post canonical system: Tag systems, which comprise a universal computational model, are notable examples of Post normal-form system, being also monogenic.
A string rewriting system is a special type of Post canonical system with a single initial word, and the productions are each of the form That is, each production rule is a simple substitution rule, often written in the form g → h. It has been proved that any Post canonical system is reducible to such a substitution system, which, as a formal grammar, is also called a phrase-structure grammar, or a type-0 grammar in the Chomsky hierarchy.