λ ⇒ ab ⇒ aabb
In the first step, we apply (13.1) with the identification x 1 =λ, V 1 = λ, x 2 = λ, y 1 =
a, W 1 = V 1 , and y 2 = b. In the second step, we re-identify V 1 = ab, leaving
everything else the same. If you continue with this, you will quickly convince
yourself that the language generated by this particular Post system is {a n b n : n ≥
0}.
Example 13.6
Consider the Post system with
C T = {1, +, =},
C N = Ø,
V = {V 1 , V 2 , V 3 },
A = {1 + 1 = 11},
and productions
V 1 + V 2 = V 3 → V 1 1 + V 2 = V 3 1,
V 1 + V 2 = V 3 → V 1 + V 2 1 = V 3 1.
The system allows the derivation
1 + 1 = 11 ⇒ 11 + 1 = 111
⇒ 11 + 11 = 1111.
Interpreting the strings of 1's as unary representations of integers, the derivation
can be written as
1 + 1 = 2 ⇒ 2 + 1= 3 ⇒ 2 + 2 = 4.
The language generated by this Post system is the set of all identities of integer