A Post canonical system (or Post system for short) is a triple , such that
is an alphabet,
The last condition basically says that in a production , must contain at least one variable, and can not contain any variables that are not already occurring in . Put it more concretely, a production in a Post canonical system has the form
Examples. Let and . Then with consisting of
is a Post canonical system, while with consisting of
is not, for the following reasons:
the antecedents in the first and fourth productions do not contain a variable
the consequents in the third and fourth productions contain variables ( in the third, and in the fourth) which do not occur in the corresponding antecedents.
Normal systems. A Post canonical system is called a Post normal system, or normal system for short, if each production has the form (called a normal production), where are words on and is a variable.
Languages generated by a Post system
Let us fix a Post system . A word is said to be immediately derivable from a word if there is a production of the form (1) above, such that
where are words (not variables). This means that if we can write a word in the form of an antecedent of a production by replacing all the variables with words, then we can “produce”, or “derive” a word in the form of the corresponding consequent, replacing the corresponding variables with the corresponding words. When is immediately derivable from , we write . Using the example above, with the production , we see that
if we set and , or
if we set and exactly one of and the other .
When is derivable from , we write . Again, following from the example above, we see that , since
Given a finite subset of words on , let be the set of all words derivable from words in . Elements of are called axioms of and elements of theorems (of derived from axioms of ). Intuitively, we see that the Post system is a language generating machine that creates the language via a set of axioms. In general, we say that a language over an alphabet is generable by a Post system if there is a Post system such that , a finite set of axioms on such that .
If a language is generable by a Post system, it is generable by a normal system.
A language is generable by a Post system iff it is generable by a semi-Thue system. In this sense, Post systems and semi-Thue systems are “equivalent”.
Instead of allowing for one antecedent and one consequent in any production, one can have a more generalized system where one production involves a finite number of antecedents as well as a finite number of consequents:
where each is a function from to . We may define to be immediately derivable from if can be expressed using each of the antecedents by substituting the variables by words , and can be expressed in at least one of the consequents by the corresponding substitutions (of into ). It can be shown that any language generated by this more general system is in fact Post generable!
It can be shown that a language is Post-generable iff it is recursively enumerable.
|Date of creation||2013-03-22 17:33:28|
|Last modified on||2013-03-22 17:33:28|
|Last modified by||CWoo (3771)|
|Defines||Post canonical system|
|Defines||Post normal system|
|Defines||generable by a Post system|