An Introduction to Formal Languages and Automata, 7th Edition

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 Π is defined by

$$\Pi =\left(C,V,A,P\right),$$

where

1. 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,
2. V is a finite set of variables,
3. A is a finite set from C^*, called the axioms,
4. P is a finite set of productions.

The productions in a Post system must satisfy certain restrictions. They must be of the form

$x_1{V}_1{x}_2\cdots V_n{x}_{n+1}\to y_1{W}_1{y}_2\cdots W_m{y}_{m+1},$

(13.1)

where x_i, y_i ∈ C^*, and V_i, W_i ∈