The Spinor Representation of Formal Languages

[Mark Hopkins]

At the basis of a notation I've developed several years ago for
Context Free Expressions (CFE's) lies a deep analogy between Quantum Physics
and Formal Language theory. This article completes this analogy, as well as
extending the CFE notation to cover all Turing languages (thus arriving at a
notation for Turing Expressions).

One can look at an automaton as comprising a state space. This space is
made linear with the inclusion of the operation (A + B) to represent
non-determinism. A + B is interpreted as the set-theoretic union for
Classical computation, but may also be interpreted as the union operation of
Quantum set theory for Quantum computation.

A class of automata defines a class of operators and an algebra defined
on those operators. These operators form a semi-ring under the operations of
concatenation and +. Since + is being interpreted as the union operation,
one can also define A* = 1 + A + AA + AAA + ... and thus arrive at the
notion of regular expressions.

The tensor product of this algebra with the free monoid comprising the
input alphabet will define an algebra over which one can then represent the
corresponding class of languages by regular expressions.

One could also form the tensor product of this algebra with a second free
monoid, representing an output alphabet, to obtain an algebra for the
corresponding class of automata with output actions. For instance, the
tensor product of two free monoids will yield a representation for
finite state machines.

Since the operators are applied to a countable state space, they can
be represented as infinite matrices. Therefore the tensor product also
leads to a finitely generated infinite matrix algebra.

In this representation, a state takes on the form of a column vector |S>;
or a spinor. One can also refer to the corresponding row vector <S|, and
define the adjoint of any operator correspondingly. This results in a
*-algebra, with the adjoint being the conjugation operator.

In addition, certain simple self-adjoint operators will then play a
special role -- the projections pS = |S><S|. Also, since one has identities
such as:
<S| |S'> = 1 if S = S'
= 0 else

one can talk about left and right annihilators.

Denote the tensor product of the operator algebra and alphabet by A.
Every regular expression, E, over the A will be factorable in the form:

E = sum (|S><S| E_S)

the left annihilator will then take on the form:

L(E) = A* PL_E
where
PL_E = sum (|S><S|: E_S = 0)

is a projection operator. A similar statement applies to right annihilators.
Therefore, the *-algebra is a Baer *-algebra. Among other things, that means
that the set of projections (self-adjoint idempotent operators) forms a
lattice. When the + operator is interpreted as the union operator of
Quantum Set Theory, the lattice is then a Quantum Logic. This forms
the basis of a deep connection between Classical and Quantum computing.


For a one-stack machine, the basic operations are (PUSH n), (POP & TEST
FOR n), (TEST FOR EMPTY), where n ranges through the stack symbols

{ 1, ..., s }

Each state can be represented in the form:

S = s1 s2 ... sn, si = 1, ..., s

and corresponding to the operators one has:

PUSH n --- un |S> = |S n>
thus
un = sum (|S n> <S|) over all states S.
and
POP n ----- vn |S n> = |S>
vn |S m> = 0 if n, m distinct
vn |> = 0
thus
vn = sum (|S> <S n|) over all states S.

So un and vn are adjoints. Finally one has

EMPTY ------- p0 |S n> = 0
p0 |> = |>
so
p0 = |> <|.

the projection operator for the empty state |>.

For each class of automata, one may formulate a completeness axiom

1 = sum (|S><S|) over all states S

which will be interpreted as saying "the automaton is in one of its
states S". For the one state machine this leads to the identity:

p0 + u1 v1 + ... + us vs = 1

which when taken with the identities:

vm un = 1 if m = n
= 0 else
vm p0 = 0 = p0 vm
un p0 = 0 = p0 un
p0^2 = p0

completely define the operator algebra.

An infinite matrix representation for this operator set can be
realised by way of the correspondence:

|w1 w2 ... wn> = w1 + w2 s + ... + wn s^{n-1}
for wi = 1, ..., s

which leads to the representation:

p0 = |0><0|
un = sum (|s S + n><S|) for S >= 0
vn = sum (|S><s S + n|) for S >= 0

For a one-symbol stack machine, the u and v operators take on the
simple form:
u1 = sum (|S + 1><S|)
v1 = sum (|S><S + 1|)

which in infinite matrix form is:

/ \ / \
| 0 1 0 0 0 ... | | 0 0 0 0 0 ... |
| 0 0 1 0 0 ... | | 1 0 0 0 0 ... |
v1 = | 0 0 0 1 0 ... | u1 = | 0 1 0 0 0 ... |
| 0 0 0 0 1 ... | | 0 0 1 0 0 ... |
| 0 0 0 0 0 ... | | 0 0 0 1 0 ... |
... ...


The class of regular expressions formed from the tensor product of
the algebra { p0, u1, ..., us, v1, ..., vs } and an input alphabet
{ x1, ..., xp } forms a *-algebra under the adjoint operator:

adj(p0) = p0
adj(ui) = vi, adj(vi) = ui
adj(xj) = xj

will define a corresponding class of languages by way of the correspondence:

L = <0| E |0>

I'm using the notation adj(x) to denote adjoints since the star is being
used elsewhere to denote the infinite union A* = 1 + A + AA + AAA + ....

This class of languages is the class of non-deterministic Context Free
Languages. Therefore, E will be a regular expression that uniquely defines
a CFL -- so it may be called a Context Free Expression. The Dyck language
over symbols pairs { b, d } and { p, q }, for instance, will correspond
to the regular expression:

(b u1 + d v1 + p u2 + q v2)*
with
Dyck(b, d; p, q) = <0| (b u1 + d v1 + p u2 + q v2)* |0>


The class of languages formed by regular expressions taken over the tensor
product of an input alphabet, an output alphabet and the algebra defined above
will correspond to the non-deterministic Simple Syntax Directed Translation
languages.

One can also arrive at a representation for a 2-stack machine by taking
the tensor product of two instances of the stack algebra. The class of
languages formed by regular expressions taken over this algebra will be
equal to the class of all Turing Computeable languages. Thus, one arrives
at a notation for Turing Expressions.

If one represents the state of the two stack machine as follows:

|S; S'>

where S and S' refer to the states of the respective stacks, taken over
the respective stack alphabets:

{ 1, 2, ..., s } for the first stack
{ 1, 2, ..., t } for the second stack.

Then the corresponding algebra will be generated by the operators:

un = sum (|S n; S'> <S; S'|), over all S and S'
vn = sum (|S; S'> <S n; S'|), over all S and S'
p0 = sum (|0, S'> <0; S'|)

Un = sum (|S; S' n> <S; S'|), over all S and S'
Vn = sum (|S; S'> <S; S' n|), over all S and S'
P0 = sum (|S; 0> <S; 0|)

with the identities

p0 + u1 v1 + ... + us vs = 1 P0 + U1 V1 + ... + Ut Vt = 1
vm un = 1 if m = n Vm Un = 1 if m = n
= 0 else = 0 else
vm p0 = 0 = p0 vm Vm P0 = 0 = P0 Vm
un p0 = 0 = p0 un Un P0 = 0 = P0 Un
p0^2 = p0 P0^2 = P0

x y = y x for x = p0, um, vn; y = P0, Um, Vn

Using the familiar 2-stack representation for Turing machines:

Left End of Tape (L) Current Position (r) Right End of Tape (R)

by the state
|L; R r>

and where both stack alphabets are identical (s = t), one can arrive at an
operator set and algebra for the Turing operators:

TEST FOR SYMBOL n: sum (|L; R n><L; R n|) = Un Vn

WRITE m: |L; m><L; | + sum |L; R m><L; R n|
= Um (P0 + V1 + V2 + ... + Vs)

GO RIGHT: |L B; ><L; | + sum |L n; R><L; R n|
= uB P0 + u1 V1 + u2 V2 + ... + us Vs.

GO LEFT: sum |L; Rn><Ln; R|
= U1 v1 + U2 v2 + ... + Us vs

The extra uB P0 term in the (GO RIGHT) operator accounts for the possibility
that the right end of the tape is extended. For symmetry, one might also
consider the possibility of a 2-way tape in which case one will have an
extra term UB p0, for (GO LEFT). The sumbol B is the Turing machine's blank
symbol which is assumed to be included in the stack alphabet. One could take
B = 1 without loss of generality.

This representation can be compacted to the following form without loss
of generality:

TEST FOR SYMBOL n: Pn = Un Vn
WRITE m & GO RIGHT: Wm = um (P0 + V1 + V2 + ... + Vs)
GO LEFT: <= = U1 v1 + U2 v2 + ... + Us vs

Every Turing Machine program will be a regular expression over this algebra.

If we allow the inclusion of an alphabet X = { x1, ..., xs }, to parallel
the stack alphabet, then we can represent the operation of the Turing machine
on an input word as follows:

(1) The input word is entered in reverse order on the
right stack
(2) The read head is started at the left (i.e., the left stack
starts empty).
(3) The program is run
(4) The read head is rewound to the left so the output will
be on the right stack
(5) The output word is extracted from the right stack in reverse
order.

Steps (1) and (2) take the algebraic form:

ENTER INPUT w1 w2 ... wn: | ; wn ... w2 w1> = U_wn ... U_w1 |; >

and step (4) takes the form:

REWIND |L; R> --> |; L' R> = p0 (<=)* |L; R>

where L' denotes the reverse of L. Then step (5) takes on the form:

EXTRACT |; R'> --> R = <; | X* |; R'>
where
X = (x1 V1 + ,.. + xs Vs)

extracts one symbol from the right stack and where R' is the reverse of R.

Thus, the action of every Turing Computation can be represented in the form:

< ; | X* p0 (<=)* E U_wn ... U_w1 | ; >

where E is the regular expression corresponding to the Turing program. Noting
that any Turing computeable language can be represented as the output of
a Turing program on a set of inputs of the form --

a b* c

then we can represent the entire language by a single Turing Expression:

L = < ; | X* p0 (<=)* E U_c U_b* U_a | ; >

where E is a regular expression (corresponding to the Turing program)
over the set:
{ P1, P2, ..., Ps, W1, W2, ..., Ws, <= }

Thus one sees that the set of regular expressions over the tensor product
of two stack algebras and an alphabet has the full generality to represent all
Turing Computeable languages. The special form, above, may be likened to a
Normal Form representation over this algebra, certainly not the only one.

One should also note that it suffices to limit the number of symbols to
2 -- taking s = 2, by using binary notation. Then it follows that the
algebra

{ p0, u1, u2, v1, v2 } x { P0, U1, U2, V1, V2 } x { x1, x2 }

is powerful enough that every Turing computable language, L, can be
represented as a regular expression, E, over it with the correspondence:

L = < ; | E | ; >