The Untold Story of Formal Language Theory 5
Mark Hopkins
The Biggest Algebra
(Note: Part 4 of the series was posted under the title "The World's Smallest
Proof of Parikh's Theorem, and will be continued in the next part of
the series with some illustrations provided showing the ease of
application of the proof to actual cases).
In earlier articles, a most amazing algebra, C2, was defined. Among its
more unusual properties was a property of self-similarity in which it was
shown to be isomorphic to its own matrix algebra. Then we showed that the
"tensor" product of C2 by R(X), the free rational monoid over X, engulfed
all of the context-free languages over X.
So is there anything this algebra CAN'T do??
No. More specifically: every recursively specifiable subset of the free
monoid over X, which we'll call X*; every recursively specifiable function
and relation between recursive subsets of X* and Y* can all be represented
within a *single* algebra -- (C2 x R(X)) x (C2 x R(Y)). Letting T(X, Y)
denote the class of all recursively specifiable translations from X to Y,
we will show that T(X, Y) (which is a rational monoid) is embedded inside
(C2 x R(X)) x (C2 x R(Y)) as a subalgebra.
(5.1) Translations
To formulate this result, a definition for T(X, Y) is provided here. It
is highly symmetric, easy to work with and includes the more standard
definition via Turing Machines as a special case.
A translation system is a finite set of translation rules. More precisely,
a translation system from X to Y consists of the following:
A symbol set Z: which contains X and Y as subsets
A finite set P of rules of the form:
z1 ... zm -> z1' ... zn'
where z1, ..., zm, z1', ..., zn' are in Z, and m, n are
non-negative integers (m = 0, n = 0 are allowed).
A translation consists of 0, 1 or more translation steps, which have the
following form:
A z1 ... zm B -> A z1' ... zn' B
where A and B are arbitrary sequences of symbols taken from Z, and
z1 ... zn -> z1' ... zn' is a rule in P.
Note the reference made by the title. Every equational algebra can be
specified by a translation system -- and actually every implicational
algebra as well if we do a little extra work to simulate implications.
We will write w |- w' if there is a translation sequence
w = w0 -> w1 -> ... -> wn = w'
where n may be 0 or any positive integer. A translation sequence w |- w'
is considered proper if w consists only of symbols from X and w' of symbols
from Y.
Note that X and Y are allowed to overlap.
The translation set generated by the system is then defined as the set:
{ (w, w'): w |- w' is a proper translation }
Given subsets LX of X*, LY of Y* we can also define:
M(LX, LY) = { (w, w'): w |- w', w in LX, w' in LY }
M(LX) = { w: w |- w' for some w' in Y* }
M'(LY) = { w': w |- w' for some w in X* }
where M refers to the translation system. We can even define more complex
combinations, e.g.,
M'(LX, LY) = { (w, w'): B w B |- B w' B, w in LX, w' in LY }
where B denotes a symbol in Z - (X union Y) -- the so-called "blank symbol".
(5.2) The Markov Machine
To make this definition more procedural, we will define a "cursor", #,
and a current "state" of the form w # w'. The following then characterizes
all the proper translations from X to Y:
(1) Read in a word # -> x1 ... xm #
(2) Apply any of the following in any order (when applicable)
any number of times:
(a) Go left z # -> # z
(b) Go right # z -> z #
(c) Reduce # z1 ... zm -> z1' ... zn' #
where (z1 ... zm -> z1' ... zn') is a rule in P.
(3) Write out a word # y1 ... yn -> #
where the x's are symbols in X, y's in Y and z's in Z.
Since this machine model doesn't really have a name (as far as I know),
I'll simply go with the default name it after myself: a Mark Machine. Now,
it does seem to have a particular Slavic feel to it and I do read and
understand some Russian, so I'll stick an -ov on the name and make it sound
fancy. So we'll call it a Markov Machine.
The corresponding process we will therefore call a Markov Process.
Wouldn't it be funny if that's what people ACTUALLY called it?
(5.3) Representing Markov Machines in (C2 x R(X)) x (C2 x R(Y)).
The algebra in the section title can also be characterized as the
rational monoid given by the following presentation:
< D union E union X union Y | C union R_D union R_E >
where
D = { b, d, p, q }
E = { B, D, P, Q }
C = the set of commutation relations xy = yx for symbols
(x, y) with x from one of the sets D, E, X, or Y and
y from another of the sets (6 combinations in all, and
I don't feel like listing them all.
R_D = the C2 relations over D: {bd = pq = 1, bq = pd = 0,
db + qp = 1 }
R_E = the corresponding C2 relations over E.
Similar to part 3 of the series, we start out with a (complete) postfix
b-p code of the set ({0} union Z), with the b-p code for element i being
denoted by <i|, the analogous B-P code by <i|', and their corresponding
adjoints by |i> and |i>' respectively.
For each rule (z1 ... zm -> z1' ... zn') we write:
[z1 ... zm -> z1' ... zn'] = |z1> ... |zm> <z1'|' ... <zn'|'
and define
[P] = sum ([p]: p is a rule in P)
Corresponding to the "go left" and "go right" moves we also define:
L = sum (|i><i|': i not 0)
and R = sum (|i>'<i|: i not 0)
Finally, corresponding to the input language LX and output language
LY (which we assume are represented by rational expressions), we can write:
<LX| = lub { <x1|...<xm|: x1...xm in LX }
|LY>' = lub { |y1>'...|yn>': y1...yn in LY }
and also:
F(LX) = lub { x1...xm <x1|...<xm|: x1...xm in LX }
G(LY) = lub { |y1>'...|yn>' y1...yn: y1...yn in LY }
For instance
<X*| = (sum <x|: x in X)*
F(X*) = (sum x <x|: x in X)*
Then we can write out the following representations:
lub M(LX) = <0|<0|' F(LX) (L + R + [P])* |LY> |0>|0>'
lub M'(LY) = <0|<0|' <LX| (L + R + [P])* G(LY) |0>|0>'
lub M(LX, LY) = <0|<0|' F(LX) (L + R + [P])* G(LY) |0>|0>'
with other more complex combinations representable in similar ways.
Proving this representation is done in essentially the same way we
proved the corresponding representation for CFL's in part 3. For
instance, the last set may be represented as:
lub { x1...xm y1...yn <0|<0|'<x1|...<xm| z1...zp |y1>'...|yn>|0>|0>' }
where the z's correspond directly to the moves of the underlying Markov
Machine. The only non-zero words are those that represent valid, proper,
translation sequences.
Also, to show that this mapping is an injection, we proceed in a manner
similar to that in part 3 by coming up with a matrix representation for
(C2 x R(X)) x (C2 x R(Y)). This is fairly routine: just take the tensor
product of the matrix representations for C2 x R(X) and C2 x R(Y), which
were presented in part 3.