the substrings x 1 , x 2 …match the corresponding strings in (13.1) and w i ∈ C*. We
can then make the identification w 1 = V 1 , w 2 = V 2 ,…, and substitute these values
for the W's on the right of (13.1). Since every W is some V i that occurs on the
left, it is assigned a unique value, and we get the new string y 1 w i y 2 W j …y m+1 . We
write this as
x 1 W 1 x 2 W 2 …x n+1 ⇒ y 1 w i y 2 w j …y m+1 .
As for a grammar, we can now talk about the language derived by a Post
system.
Definition 13.4
The language generated by the Post system II = (C, V, A, P) is
Example 13.5
Consider the Post system with
C T = {a, b},
C N = Ø,
V = {V 1 },
A = {λ},
and production
V 1 → aV 1 b.
This allows the derivation