Post Canonical System

Get Post Canonical System essential facts below. View Videos or join the Post Canonical System discussion. Add Post Canonical System to your PopFlock.com topic list for future reference or share this resource on social media.
## Definition

### Example (well-formed bracket expressions)

## Normal-form theorem

## String rewriting systems, type-0 formal grammars

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Post Canonical System

A **Post canonical 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. Today they are mainly of historical relevance because every Post canonical system can be reduced to a string rewriting system (semi-Thue system), which is a simpler formulation. Both formalisms are Turing complete.

A **Post canonical system** is a triplet (**A**,**I**,**R**), where

**A**is a finite alphabet, and finite (possibly empty) strings on**A**are called*words*.**I**is a finite set of*initial words*.**R**is a finite set of string-transforming rules (called*production rules*), each rule being of the following form:

where each g and h is a specified __fixed__ word, and each *$* and *$' * is a __variable__ standing for an arbitrary word. The strings before and after the arrow in a production rule are called the rule's *antecedents* and *consequent*, respectively. It is required that each *$' * in the consequent be one of the *$*s in the antecedents of that rule, and that each antecedent and consequent contain at least one variable.

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

Alphabet: {[, ]} Initial word: [] Production rules: (1)$→ [$] (2)$→$$(3)$_{1}$_{2}→$_{1}[]$_{2}Derivation of a few words in the language of well-formed bracket expressions: [] initial word [][] by (2) [[][]] by (1) [[][]][[][]] by (2) [[][]][][[][]] by (3) ...

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:

- Given any Post canonical system on an alphabet
**A**, a Post canonical system in*normal form*can be constructed from it, possibly enlarging the alphabet, such that the set of words involving only letters of**A**that are generated by the normal-form system is exactly the set of words generated by the original system.

Tag systems, which comprise a universal computational model, are notable examples of Post normal-form system, being also *monogenic*. (A canonical system is said to be *monogenic* if, given any string, at most one new string can be produced from it in one step — i.e., the system is deterministic.)

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.

- Emil Post, "Formal Reductions of the General Combinatorial Decision Problem,"
*American Journal of Mathematics***65**(2): 197-215, 1943. - Marvin Minsky,
*Computation: Finite and Infinite Machines*, Prentice-Hall, Inc., N.J., 1967.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists