(a) L (a*b + ab*c).
(b) L = {ww}.
(c) L = {a n b n c n }.
2. Find a Post system that generates
L = {ww R : w ∈{a, b}*}
3. For Σ = {a}, what language does the Post system with axiom {a} and the
following production generate?
V 1 → V 1 V 1 .
4. What language does the Post system in Exercise 3 generate if the axiom set is
{ a, ab} ?
5. Find a Post system for proving the identities of integer multiplication using
unary notation and starting from the axiom 1 * 1 = 1.
6. Give the details of the proof of Theorem 13.6.
7. What language does the Post system with
V → aVV
and axiom set {ab} generate?
8. A restricted Post system is one on which every production x → y satisfies, in
addition to the usual requirements, the further restriction that the number of
variable occurrences on the right and left is the same, i.e., n = m in (13.1).
Show that for every language L generated by some Post system, there exists
a restricted Post system to generate L.
13.3 Rewriting Systems
The various grammars we have studied have a number of things in common with
Post systems: They are all based on an alphabet in which strings are written, and
some rules by which one string can be obtained from another. Even a Turing
machine can be viewed this way, since its instantaneous description is a string
that completely defines its configuration. The program is then just a set of rules