The Untold Story of Formal Language Theory 2
Mark Hopkins
In this article and ones to follow in this series I will be adopting more
of a monograph style, with numbered sections, section titles and so on, since
this is for all intents and purposes a monograph.
In the previous account, I asked the question "what if formal languages
had been unknown until now and had been discovered only today?" and provided
a purely algebraic answer. The operations associated with regular languages
(A, B |-> A + B, A B, A*) are seen to be more than sufficient to represent
all computeable languages and all compuetable subsets of a monoid, if only
we allow the underlying algebra to be non-free.
The answer provided also has Category Theoretic overtones, and possesses
a strongly Universal Algebra flavor, in the way we defined a Ratioal Monoid,
and the ability to generalise this concept to Rational Category.
Essentially this is a new foundation of Formal Languages (the basis of
Computer Science), in which the language expression (regular expression,
context free expression, Turing expression, etc.) and systems of equations
over them play the primary role. All the other concepts, such as grammars
and automata are then represented by systems of equations that carry
certain symmetry properties. The expressions and systems that correspond
to one and two stack machines will happen to bear a close formal similarity
to the kinds of objects you might see on Quantum Theory.
Here I'll explore this seemingly mysterious, and further develop the
theory and notation for Context Free Expressions. In addition, some of
the results quoted previously will be expanded on in more detail here and
in the following.
(2.1) The Spinor Algebra C2 x M
Previously I used the notation A x B to denote the "tensor" product of
the rational monoids A and B, whereas in Universal Algebra this is used to
represent the "direct product". The notation is borrowed from Linear Algebra
whose corresponding "direct product" is the "direct sum" A + B. For example,
C x H denotes the "complex Quaternions", where H is the Quaternions and
C the complex numbers, and C x H is isomorphic to the Pauli Spin algebra,
or M2(C), the complex 2 x 2 matrices. On the other hand, R + R represents
the "dual reals", which would be distinct from R x R (which is isomorphic
to R, itself).
The algebras I use here bear a formal similarity to what you might see
in Quantum Theory. In fact, take a closer look at C2 and its defining
relations:
bd = pq = 1, bq = pd = 0, db + qp = 1
Notice how those tail thingeys hanging off the letters point up and down
as if they're trying to say "spin up" and "spin down", and how the
symmetric arrangement of the letters nearly screams out "adjoints". With
the following correspondences
b <--> <+|, d <--> |+>
p <--> <-|, q <--> |->
the relations become even more suggestive:
<+| |+> = 1 = <-| |->, <+| |-> = 0 = <-| |+>
|+> <+| + |-> <-| = 1
Therefore, I will call C2 (C2 x M) the "2-component Spinor Algebra (over M)".
The significance of this algebra, as you'll see, is that when M = R(X), the
algebra of regular languages over X, then C2 x M will contain an isomorphic
copy of the algebra of context free languages over X, thus leading to the
notion of "Context Free Expressions". A similar consideration would also
allow us to arrive at the "Turing Expressions", representing all the
computeable languages over X, corresponding to the algebra C2 x C2 x R(X),
and "push down transductions" or "turing transductions" corresponding
respectively to the algebras C2 x R(X) x R(Y) and C2 x C2 x R(X) x R(Y),
though we won't go in detail here on these latter issues.
With the operation a + b = lub { a, b }, the algebra C2 x M will form
a *-semiring, in which the adjoint relation is that generated by the
following correspondences:
b <--> d, p <--> q, x self adjoint for x in M
Even more, one finds the occurrences of projection operators, such as
qp and db, which are also orthocomplements of one another in virtue of
the relation
db + qp = 1
However, there are also projections, such as d* b* = 1 + d* d + b b*,
which cannot have an orthocomplement since neither d* d <= 1, nor b b* <= 1.
So somewhere buried inside C2 x M is a Baer-* semiring, representative of
an underlying ortholattice structure.
Perhaps this provides the bridge between Classical Computation and
Quantum Computation in a way analogous to how Poisson Brackets bridge
between Classical and Quantum Mechanics? That's the mystery of the
connection...
(2.2) Spinor Algebras and Codes
Making use of the analogy presented above, we'll define the n-component
Spinor Algebra Cn as the rational monoid generated by the set:
{ <0|, <1|, ..., <n-1|, |0>, |1>, ..., |n-1> }
subject to the relations
<i| |j> = delta[i, j]
|0> <0| + |1> <1| + ... + |n-1> <n-1| = 1
where delta[i, j] is the Kroenecker Delta defined by
delta[i, j] = 1 if i = j, 0 else
There is no increase in generality in considering these algebras, in
relation to C2 since Cn can be embedded into C2 by the use of a suitable
binary coding. However, the details also happen to reveal some interesting
connections to some of the more common concepts in Coding Theory, and could
even be taken as an alternate means of defining these concepts. So it'll
be reviewed here.
Let f be a binary code of the set { 0, 1, ..., n - 1 }. Define
f'(<m|) = <k_1> <k_2> ... <k_l>,
where
f(m) = k_1 k_2 ... k_l
<0> = b, <1> = p
and let f'(|m>) be the adjoint of f'(<m|). Then the following properties
will hold:
(A) f'(<i|) f'(|j>) = delta[i, j] <==> f is a postfix code
(B) f'(|0>) f'(<0|) + ... + f'(|n-1>) f'(<n-1|) = 1
<==> f is a complete code
Thus
(C) f extends to an embedding f': Cn -> C2
<==> f is a complete postfix code.
This leads to a possible alternate definition:
DEF: A complete postfix b-p code is a subset { u_0, u_1, ..., u_{n-1} }
of the set (b + p)* of words in { b, p }, such that:
u_i v_j = delta[i, j]
v_0 u_0 + v_1 u_1 + ... + v_{n-1} u_{n-1} = 1
where v_i is defined as the adjoint of u_i, 0 <= i < n.
EXAMPLE: { b, bp, pp } is a complete postfix b-p code since
(A) db + qdbp + qqpp = db + q (db + qp) p = db + qp = 1
(B) b d = 1, b qd = 0, b qq = 0,
bp d = 0, bp qd = 1, bp qq = 0,
pp d = 0, pp qd = 0, pp qq = 1
(2.3) C2 is isomorphic to M2(C2).
This is probably the more remarkable property of C2 and has some
interesting applications as will be seen. The correspondence is as
follows:
A B <--> d A b + d B p + q C b + q D p
C D
Preservation of sums and products is trivial:
Sums: A B + E F <--> (dAb + dBp + qCb + qDp) + (dEb + dFp + qGb + qHp)
C D G H
which, by distributivity, commutativty and other semi-ring properties can
be rewritten in the form:
d (A + E) b + d (B + F) p + q (C + G) b + q (D + H) p
which corresponds to the matrix sum.
Products: A B E F <--> (dAb + dBp + qCb + qDp)(dEb + dFp + qGb + qHp)
C D G H
which can be written out in the form:
( (dA+qC) b + (dB+qD) p ) (d (Eb+Fp) + q (Gb+Hp) )
and in virtue of the cancellation properties bd = pq = 1, bq = pd = 0:
(dA+qC) (Eb+Fp) + (dB+qD) (Gb+Hp)
or
d (AE+BG) b + d (AF+BH) p + q (CE+DG) b + q (CF+DH) p
which corresponds to the matrix product.
The preservation of the star is the most substantial property. For
this, we use the following algebraic properties of rational expressions:
a (b a)* = (a b)* a, (a + b)* = a* (b a*)* = (a* b)* a*
and the identities:
(d R b)* = 1 + d R b (d R b)*
= 1 + d R (b d R)* b
= qp + db + d R (R)* b
= qp + d (1 + R R*) b
= qp + d R* b
(d R p)* = 1 + d R p (d R p)*
= 1 + d R (p d R)* p
= 1 + d R 0* p
= 1 + d R p since 0* = 1 + 0 0* = 1
and similarly:
(q R p)* = db + q R* p
(q R b)* = 1 + q R b
Thus, we find:
(d A b + d B p + q C b + q D p)*
= (qp + d A* b) ( (dBp + qCb + qDp) (qp + d A* b) )*
= (qp + d A* b) (dBp + q C A* b + qDp)*
= (qp + d A* b) (db + q D* p) ( (dBp + q C A* b) (db + q D* p) )*
= (d A* b + q D* p) (d B D* p + q C A* b)*
= (d A* b + q D* p) (1 + d BD* p) ( q CA* b (1 + d BD* p) )*
= (d A* b + d A*BD* p + q D* p) (q CA* b + q CA*BD* p)*
which after expanding q C A* D B* p and performing a few more manipulations,
will ultimately yield:
d (A* B D* C)* A* b + d (A* B D* C)* A* B D* p
+ q (D* C A* B)* D* C A* b + q (D* C A* B)* D* p
which corresponds to the matrix
/ A B \ * = / (A* B D* C)* A* (A* B D* C)* A* B D* \
\ C D / \ (D* C A* B)* D* C A* (D* C A* B)* D* /
The relation of this matrix to finite automaton is well-known in
formal language theory, and we'll explore this relation in more detail,
as well as the relation of C2 x M to Push Down Automaton (not so
well-known, not known at all in fact!), in the following.