Post canonical system
Encyclopedia
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 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 simpler a formulation. Both formalisms are Turing complete.
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 precisely the recursively enumerable languages.
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)
][[] by (3)
...
Post 1943 proved the remarkable Normal-form Theorem, which applies to the most-general type of Post canonical system:
Tag system
s, 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.)
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
.
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. 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 simpler a formulation. Both formalisms are Turing complete.
Definition
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
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
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 precisely the recursively enumerable languages.
Example (well-formed bracket expressions)
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)
][[] by (3)
...
Normal-form theorem
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 system
Tag system
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite state machine whose only tape is a FIFO queue of unbounded length,...
s, 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.)
String rewriting systems, Type-0 formal grammars
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
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
, is also called a phrase-structure grammar, or a type-0 grammar in the Chomsky hierarchy
Chomsky hierarchy
Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
.