13.2 Post Systems
A Post system looks very much like an unrestricted grammar consisting of an
alphabet and some production rules by which successive strings can be derived.
But there are significant differences in the way in which the productions are
applied.
Definition 13.3
A Post system II is defined by
II = (C,V,A,P),
where
C is a finite set of constants, consisting of two disjoint sets C N , called the
nonterminal constants, and C T , the set of terminal constants,
V is a finite set of variables,
A is a finite set from C*, called the axioms,
P is a finite set of productions.
The productions in a Post system must satisfy certain restrictions. They must be
of the form
where x i , y i ∈ C*, and V i , W i ∈ V, subject to the requirement that any variable
can appear at most once on the left, so that
V i ≠ V j for i ≠ j,
and that each variable on the right must appear on the left, that is,
Suppose we have a string of terminals of the form x 1 w 1 x 2 w 2 …w n x n+1 , where
A Post system looks very much like an unrestricted grammar consisting of an
alphabet and some production rules by which successive strings can be derived.
But there are significant differences in the way in which the productions are
applied.
Definition 13.3
A Post system II is defined by
II = (C,V,A,P),
where
C is a finite set of constants, consisting of two disjoint sets C N , called the
nonterminal constants, and C T , the set of terminal constants,
V is a finite set of variables,
A is a finite set from C*, called the axioms,
P is a finite set of productions.
The productions in a Post system must satisfy certain restrictions. They must be
of the form
where x i , y i ∈ C*, and V i , W i ∈ V, subject to the requirement that any variable
can appear at most once on the left, so that
V i ≠ V j for i ≠ j,
and that each variable on the right must appear on the left, that is,
Suppose we have a string of terminals of the form x 1 w 1 x 2 w 2 …w n x n+1 , where