The Algebraic Representation of Formal Languages

[Mark Hopkins]

This is a continuation of the series of articles:

The Spinor Representation of Formal Languages
The Formal Language Representation of Algebras
The Equational Representation of Formal Languages
Context Free Expressions
The Hardest Context Free Language

posted here over the last several days in which the underlying algebras will
be discussed along with applications to the problems

Regular Expression -> Finite State Automaton
* The Brzozowski method for RE -> DFA conversion.
* An RE -> NFA algorithm.

(0) Algebraic Preliminaries
In earlier articles, the use of linear algebras, vector spaces and
derivability were mentioned several times:

From "The Spinor Representation of Formal Languages":
> 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 ...

Technically this is not a linear space since there is no underlying field.
In fact, the additive system does not even comprise a group, but rather an
abelian monoid in which every element is idempotent (x = x + x).

A ring is an algebra which forms an abelian group under addition and a
semigroup under multiplication and in which the multiplication is distributive
over addition. If the ring has a unity then the multiplicative semigroup
becomes a monoid (since monoid = semigroup with identity).

In contrast, if the addition operation only forms an abelian semigroup,
then the algebra is known as a semi-ring. This seems to be a rare concept
since I have never seen it discussed in any abstract algebra text.

Since this addition operation is also idempotent, one might also term this
as a "Partially Ordered Semi-Ring" or perhaps a "Semi-Ring, Semi-Lattice".
In particular, one can form the definition:

A <= B iff A + B = B

That this is a partial order (with 0 as the smallest element) is verified by
the following:

(0) 0 <= A since 0 + A = A
(R) A <= A since A + A = A
(T) If A <= B, B <= C
then A + C = A + (B + C) = (A + B) + C = B + C = C
therefore A <= C
(A) If A <= B, B <= A
then B = A + B = B + A = A

which uses all the properties of the abelian additive monoid (identity,
associativity and commuitativity) as well as idempotency. That it's a
semi-lattice is verified by the following:

* A <= A + B since
A + (A + B) = (A + A) + B = A + B
* B <= A + B since
B + (A + B) = (A + B) + B = A + (B + B) = A + B
* If A <= C, B <= C
then (A + B) + C = A + (B + C) = A + C = C
therefore A + B <= C.

The relation of derivability in "The Hardest Context Free Language" can
be interpreted as follows:

A -> B iff B <= A.

and in general this relation over the set of language expressions, which
forms a partially ordered semi-ring; over automata, which also forms a
partially ordered semi-ring as follows from the article "The Formal Language
Representation of Algebras" (actually the automata notation developed there
was applied generally to all rings, so this comment is only pertinent when
it's applied to the semi-ring comprising language expressions).

When addition is idempotent it makes sense to discuss the operator

A* = 1 + A + A A + A A A + ...

as least fixed point solution to the equation:

x = 1 + A x

Since, again, there is no name that I'm aware of to apply to partially
ordered semi-rings closed under this operation, I will call it REGULAR.
Therefore, a regular semi-ring is one in which:

x = x + x
and closed under x* = 1 + x + x x + x x x + ...

When the + operator is given a set theoretic interpretation as union then
the closure property is guaranteed by the Union Axiom. More generally,
if the underlying partial order is complete (or even "semi-complete")
then this operation can be defined.

The closure property cannot be finitely axiomatized in terms of a set of
basic equations (this is a well-known result from the theory of regular
expressions). However, one can break down the property into the following:

A* = 1 + A A*
If x = A + B x then B* A <= x.
Rquality holds unless 1 <= A.
Examples:
1 + A* = A*:
1 + A* = 1 + (1 + A A*) = (1 + 1) + A A* = 1 + A A* = A*

A* A* = A*:
Let x = A* A*. Then x = (1 + A A*) A* = 1 + A A* + A (A* A*)
= 1 + A (1 + A*) A* = 1 + A x
Thus A* <= x. Similarly x = A* A* = (1 + A*) A* = A* + x
This x <= A*.

A A* = A* A:
Let y = A A*. Then y = A (1 + A A*) = A + A y.
Thus A* A <= y. Unless 1 <= A, this becomes an equality.
If 1 <= A then
A* A + 1 = A* (A + 1) + 1 = A* A + A* + 1 = A* A + A* = A* A
and
A* A = A* (1 + A) = A* A + A* = A* A + 1 + y = A* A + y
So
y <= A* A.

The task of proving equalities is equivalent to that of minimalizing a
DFA. In view of the correspondence between automata and systems of equations
this equivalence is transparent.

From "Context Free Expressions" (in reference to the Context Free Algebra):
> This algebra can be realised using tensor space over V* of an
>(s+1)-dimensional vector space V (recall, s = the size of the stack alphabet)
>by making the idenfications:
>
> un = |n> vn = <n|
>
>where |n> is the nth element of the V and vn the adjoint basis element of V+.
>The quotient is taken with respect to the relations:
>
> <n| |n'> = 1 if n = n', 0 otherwise (R)
> |0><0| + |1><1| + ... + |n><n| = 1

(which should be |0><0| + |1><1| + ... + |s><s| = 1).

The same general comment applies. The "scalars" in this "vector space" do
not comprise a field, nor even a ring, but a semi-ring. The analogue to a
vector space when the underlying system is a ring is called a module.
When the underlying system is only a semi-ring it has no name as far as
I'm aware, so I'll call it a semi-module.

A Context Free Algebra is therefore a semi-module which contains as a
subset the free monoid X* (where X is the alphabet) and also contains as
a subset the semi-ring of regular expressions over X. The context free
algebra can thus be defined as the smallest regular semi-ring containing
the set
X union { |0>, <0|, |1>, <1|, ..., |s>, <s| }

with the relations:

<n| |n'> = 1 if n = n', 0 otherwise
|0><0| + |1><1| + ... + |n><n| = 1
x |n> = |n> x, x <n| = <n| x.


(1) Revisiting the Regular Expression to DFA Problem

(1.0) Introduction
In the past, this is a question that has been brought up on a few
occasions. The method described here is, in fact, a very old method for
reducing regular expressions to finite automata that dates back to the
early 1960's.

The RE -> DFA method was developed by Brzozowski (and is something I came
across independently, along with the RE -> NFA method to be discussed later).
At that time, in the late 1950's and early 1960's, there seemed to have
been a distinct tendency to view languages and automata as algebraic
and equational systems. This emphasis was neglected for nearly 30 years,
partly because of the inability to extend this highly algebraic idea of
regular expressions to more general concepts like context free expressions,
turing expressions and so on.

The RE -> NFA method evolved from a hand algorithm that I've been using
for years and represents what I believe is the natural method that most
people.

Software that embodies these methods can be found in the following
locations (last I checked):

ftp.cs.washington.edu::pub/pardo/regex.tar.Z.
iecc.com::pub/files/regex.tar.gz.
avahi.inria.fr::/pub/regex.tar.gz.


To carry out the conversion involves performing algebraic manipulations on
regular expressions to arrive at an automaton. The result form will be a
finite system of equations of the form:

Q = 1 + x1 Q1 + x2 Q2 + ...
or Q = x1 Q1 + x2 Q2 + ...

which represents the automaton. The meaning of the terms is as follows:

Q = 1 + ... -- means Q is a final state
Q = ... + x Q' ... -- means Q has a transition to Q' on x

and that's the ultimate basis for the correspondence between automata
and equations. This correspondence was the focus of the article

"The Equational Representation of Formal Languages"

(1.1) Regular Expressions, Monoids and Regular Semi-Rings
A regular expression over an alphabet, X, can be built out of the following
items and operations:

(0) 0 ------- to denote the empty set.
(1) 1 ------- to denote the empty string in X*.
(2) x ------- an element of X.
(3) [A] ----- denotes the regular expression 1 + A.
(4) A+ ------ denotes the regular expression A A*.
(5) A* ------ ITERATION (the set 1 + A + A A + A A A + ...)
(6) A + B --- ALTERATION (the union of A and B)
(7) A B ----- CONCATENATION

the following operation may also be included:

(8) A - B --- DIFFERENCE (the set difference of A and B).

For example, these are valid regular expressions:
(a [b+ a*])+ + c* a b (E1)
a* (b a*)* (E2)

Strictly speaking neither of the operations in (3) nor (4) is necessary since
they are defined in terms of the other operations, but are included to make
the algorithm more practical. The other operations in (1)-(7) make the set
of regular expressions a regular semi-ring.

One can represent Regular Expressions in a more formal setting as
follows:
(1) You are given an monoid, M. A monoid is an algebraic set
with an identity (1) and product operation satisfying the
properties:
a(bc) = (ab)c
a1 = 1 = 1a

(2) This monoid is generated from a finite set
X = { x1, x2, x3, ..., xn }
that represents its "alphabet". Every element of M is a
finite product of elements of X.

(3) This monoid is freely generated. That means that if
a1 a2 ... am = b1 b2 ... bp, with ai, bj in X
then
p = m, and bi = ai for i = 1 to m

This monoid is also Universal. That means for every other monoid, M',
that satisfies (1) and (2), there is a mapping f: M -> M' such that:

* f(1) is the identity in M'
* f(p q) = f(p) f(q)

One can form certain kinds of subsets over M as follows:

x -- used to denote a single element in X union { 1 }
0 -- the empty set
A B -- { a b: a in A, b in B }
A + B -- A union B
A+ -- { a1 a2 ... am: m > 0 and ai in A }
A* -- 1 + A+

They have the following properties, among others:

0 A = 0 = A 0 0 + A = A = A + 0
(A B) C = A (B C) (A + B) + C = A + (B + C)
1 A = A = A 1 A + A = A
A(B + C) = AB + AC A + B = B + A
(B + C)A = BA + CA

in addition to the:
Least Fixed Point Property
A* B is the smallest set satisfying the equation:
x = B + A x
(unless A = 1 + A)

which are the axioms for a regular semi-ring, as discussed above.

Those subsets formed from the empty set and single element sets by the
operations above are called Regular Subsets of the monoid M. Thus, the
class of regular expressions forms the smallest regular semi-ring which
contains the free monoid M = X*.

The operator A - B can also be introduced:

A - B -- { x: x in A but not in B }

and it turns out that regular subsets are closed under this operation. The
proof of this property actually emerges for free out as a consequence of the
construction outlined below.

(1.2) Automaton = System of Equations
The goal in converting a regular expression to a DFA is to get a series of
linear equations between a number of regular expressions Q0, Q1 ... Q{q-1},
with Q0 being identified as the original expression. For example, systems
of equations corresponding to the regular expressions (E1) and (E2) above are:

(a [b+ a*])+ + c* a b (S1)
Q0 = a Q1 + c Q2 (Q0 = (a [b+ a*])+ + c* a b)
Q1 = 1 + a Q1 + b Q1 (Q1 = (a + b)*)
Q2 = a Q3 + c Q2 (Q2 = c* a b)
Q3 = b Q4 (Q3 = b)
Q4 = 1 (Q4 = 1)

a* (b a*)* (S2)
Q0 = 1 + a Q0 + b Q0

The right hand side of each equation is a sum of terms of one of the forms:

x Q or 1

Because all the Q's appear only once in each term, and as a factor on the
right hand side of the term, the system is known as a Right Linear System.

As discussed above and in "The Equational Representation of Formal
Languages", an automaton is viewed as a diagrammatic depiction of a system of
equations with the following relations:

States ............... Expressions Q0, Q1,..., Q{q-1}
Start State .......... Q0
Q a final state ...... Q = 1 + ...
Arcs Q --[x]--> Q' ... Q = ... + x Q' + ...

The transition function (or more generally, the transition relation) of
the automaton is thus represented directly as the system itself.

Formally, if the transition function of the automaton is d: Q x X -> Q,
where Q is the set of states, and if \Q is defined to be 1 when Q is a
final state, and 0 otherwise, then the system of equations derived from the
automaton can be represented compactly as:

Q = \Q + sum for all x in X: (x d(Q, x))

Since this correspondence is so readily transparent, I will cease making a
distinction between an automaton and its corresponding system and will
consider an automaton to be nothing more than a fancy way of depicting that
systemn. The economy of thought engendered by this point of view will quickly
grow on you.

Exercise:
Draw the automata corresponding to the systems S1 and S2 described above,
using this correspondence.

(1.3) The Factoring Property
Every regular expression over the alphabet X is a set of words taken
from X. If this expression is denoted E, then define the following:

\E = 1 if 1 is contained in the regular expression E
= 0 else

x\E = { w: x w is contained in E }, for all x in X

The latter operator bears a degree of resemblance to the partial derivative
operator and so the same name is sometimes used, along with the partial-d
notation (not available in ASCII).

Take any element of the regular subset E. It's a word in X*. Either this
word is the empty word (in which case \E = 1), or it begins with a symbol, x,
and has the form x w (in which case w is in the set x\E, and x w in the set
x (x\E)). Thus one arrives at the FACTORING PROPERTY:

E = \E + sum for all x in X: x (x\E)

Any method used to perform this decomposition will, as a consequence,
convert a regular expression into a system of Right Linear Equations -- a
finite automaton.

(1.4) Factoring Regular Expressions
From the definitions of \E and x\E, you can derive the basic properties,
with respect to which the calculations can be carried out. Experience proves
that it's actually better NOT to calculate each of the x\E's individually, but
rather en masse. Therefore, define the Total Differential Operator:

dE = sum x (x\E)

A consequence of this definition is that:

E = \E + dE

Exercise: The properties listed in the table should be evident. Prove them.

E \E x\E dE
0 0 0 0
1 1 0 0
x 0 1 x
y 0 0 y
[A] 1 x\A dA
A* 1 x\A A* dA A*
A+ \A x\A A* dA A*
A B \A \B \A x\B + x\A B \A dB + dA B
A + B \A + \B x\A + x\B dA + dB
A - B \A - \B x\A - x\B dA - dB

where it's assumed that x and y are distinct. Note that:

1 - 1 = 0, 1 - 0 = 0,
0 - 0 = 0, BUT 0 - 1 = 0

in this algebra.

(1.5) Calculation Method
The calculation method comes straight out of the table. To decompose
a regular expression into its factors, apply a set of algebraic rules such
as the following:

(a) (A B) C = A (B C)
x = x 1, where x is any symbol
1 A = A
(A + B) + C = A + (B + C)
A + B = B + A

(b) (A + B) C = A C + B C
A + A = A
0 + A = A
x A + x B = x (A + B)
x A - x B = x (A - B)
A - A = 0
0 - A = 0

and the following transformations:

[A] = 1 + dA
A* = 1 + dA A*
A+ = \A + dA A*
A B = (\A \B) + \A dB + dA B
A + B = (\A + \B) + (dA + dB)

using the table to calculate the terms \A, \B, dA, dB. It is to be
understood that these reductions only apply to the expression itself, NOT
TO ANY OF ITS SUBEXPRESSIONS. Apply rules (b) as needed to collect all
the like terms, and apply rules (a) and (b) as needed to get the final
result. This system of reduction rules, by the way, will always
lead to the desired result in a finite number of steps, because the terms
being operated on by the dA and \A operators grow progressively smaller as
you carry out the reduction.

The result of this calculation is the state of the resulting finite
automata corresponding to the original expression. To calculate the other
states, you will then have to decompose each of the expressions appearing
in the factoring that have not already been decomposed. An implementation
will take care to store the expressions encountered in an associative table
in order to avoid duplications.

(1.6) Examples
(a* b)* a* (E3)

d ( (a* b)* a* ) = d(a* b) (a* b)* a* + da a*
= (a a* b + b) (a* b)* a* + a a*
= a (a* b (a* b)* + a*) a* + b (a* b)* a

d ( a* b (a* b)* a* + a*) = a a* b (a* b)* a* + b (a* b)* a* + a a*
= a (a* b (a* b)* a* + a*) + b (a* b)* a*

\ ( (a* b)* a*) = \(a* b)* \a* = 1 1 = 1
\ ( a* b (a* b)* + a*) = \(a* b (a* b)*) + \a* = \(a* b (a* b)*) + 1 = 1

Resulting from this is a 2-state finite automaton given by the system of
equations:

Q0 = 1 + a Q1 + b Q0 (Q0 = (a* b)* a*) (S3)
Q1 = 1 + a Q1 + b Q0 (Q1 = a* b (a* b)* a* + a*)

A minimalization step can be added to eliminate equivalent terms, which
will lead to a 1-state minimal DFA (Q0 = 1 + a Q0 + b Q0). In the
presence of the difference operator it will also be necessary to add in an
extra state for the expression 0:

0 = x1 0 + x2 0 + ... + xn 0

States proven equivalent to this one during the minimalization process will
be what are called Useless States (those that generate no words).

It's not well-known that the useless state reduction algorithm often
discussed in relation to finite automata is actually redundant and can be
incorporated under the minimilization algorithm by the inclusion of the
0 state, but this way of doing things is more economical.

It's with the minimilization step where the Least Fixed Point Property
enters into play here. The inability to directly encode minimilization as
a finite system of algebraic reduction rules is thus directly related to
the inability to represent the underlying algebra by a finite system of
equational axioms.

An example that uses the difference operator is the following:

(a + b)* - b* a a b* (E4)

For convenience, label the following expressions (I'm cheating by looking
ahead):
Q3 = (a + b)*
Q0 = (a + b)* - b* a a b* = Q3 - b* a a b*
Q1 = (a + b)* - a b* = Q3 - a b*
Q2 = (a + b)* - b* = Q3 - b*

then:
\Q3 = \(a + b)* = 1
d Q3 = (a + b)(a + b)* = a Q3 + b Q3

\Q0 = \Q3 - \(b* a a b*) = 1 - 0 = 1
d Q0
= d Q3 - d (b* a a b*)
= a Q3 + b Q3 - (b b* a a b* + a a b*)
= a (Q3 - a b*) + b (Q3 - b* a a b*)
= a Q1 + b Q0

\Q1 = \Q3 - \(a b*) = 1 - 0 = 1
d Q1
= d Q3 - d(a b*)
= a Q3 + b Q3 - a b*
= a (Q3 - b*) + b Q3
= a Q2 + b Q3

\Q2 = \Q3 - \b* = 1 - 1 = 0
d Q2
= d Q3 - d b*
= a Q3 + b Q3 - b b*
= a Q3 + b ( Q3 - b*)
= a Q3 + b Q2

The result is a 4 state automaton:

Q0 = 1 + a Q1 + b Q0 (S4)
Q1 = 1 + a Q2 + b Q3
Q2 = a Q3 + b Q2
Q3 = 1 + a Q3 + b Q3

(1.7) Complexity
All algorithms for converting Regular Expresions to DFA's will generate at
least an exponential number of states in the worst case. In particular, the
regular expression:
(a + b)* a (a + b)^n

has a 2^(n+1) state minimal DFA. There are algorithms that will convert
regular expressions into NFA's in linear time, however. One is about to be
presented below.

(1.8) Conversion to an NFA
The efficiency of the process arises because the rule:

x A + x B = x (A + B)

is no longer used. This rule is responsible for spawning the new states
that can lead to an exponential blowup in the size of the automaton.

Here we make use of the following definition:

<>: Regular Expresion -> Set of Terms of form 1 and x E
<0> = { } <0 C> = { }
<1> = { 1 } <1 C> = <C>
<x> = { x 1 } <x C> = { x C }
<A + B> = <A> union <B> <(A + B)C> = <A C> union <B C>
<A*> = {1} union <A+> <A* C> = <C> union <A+ C>
<A+> = <A A*> <A+ C> = <A (A* C)>
<[A]> = {1} union <A> <[A] C> = <C> union <A C>
<(A B) C> = <A (B C)>

Notice that this definition is actually cyclic. One has, for instance,

<A* C> = <C> union <A+ C> = <C> union <A (A* C)>

and the latter term may ultimately reduce to an expression involving <A* C>.
To arrive at a unique answer, one must ultimately apply the Least Fixed
Point property along the way:

If during the course of a reduction, one arrives at an
equation of the form

<E> = ... + <E> + ...

then eliminate the <E> on the right hand side.

When an expression is reduced, it will yield a system of equations as
follows:
E = \E + sum { x Q: x Q is in the set <E> )
where \E = 1 if 1 is in the set <E>, 0 else

Each of the Q's then is an expression which represents another state. When
these are reduced, and any new states that result, the result will be the
NFA.

As an illustration, we'll convert the expression:

(a + b)* a (a + b) (a + b) (a + b)

to arrive at an NFA. For ease of reference, we'll denote the key
subexpressions as follows:

Q0 = (a + b)* a (a + b) (a + b) (a + b)
Q1 = (a + b) (a + b) (a + b)
Q2 = (a + b) (a + b)
Q3 = (a + b)
Q4 = 1

Then we can write:

<Q0> = <(a + b)* E2>
= <a Q1> union <(a + b) Q0>
= <a Q1> union <a Q0> union <b Q0>
= { a Q1, a Q0, b Q0 }
<Q1> = <(a + b) Q2>
= <a Q2> union <b Q2>
= { a Q2, b Q2 }
<Q2> = <(a + b) Q3>
= <a Q3> union <b Q3>
= { a Q3, b Q3 }
<Q3> = <a + b>
= <a> union <b>
= < a 1, b 1 } = { a Q4, b Q4 }
<Q4> = <1> = { 1 }

Thus, you get the following system of equations:

Q0 = a Q0 + b Q0 + a Q1
Q1 = a Q2 + b Q2
Q2 = a Q3 + b Q3
Q3 = a Q4 + b Q4
Q4 = 1

The corresponding DFA has 16 states, which arises ultimately from trying
to combine (a Q0) and (a Q1) into a (Q0 + Q1) and then combining all the
like terms in the resulting state Q0 + Q1, and so on.

(1.8) Derivation Sequences = System of Inequalities
Since regular expressions form a partially ordered semi-ring, one can
define an inequality relation over them. As per our previous discussion,
this relation will be denoted by ->. Thus:

A -> B iff A = A + B

Then the following properties hold:

(a) A -> \A, A -> x x\A, A -> dA
(b) A -> B if and only if \A -> \B and x\A -> x\B
(c) A -> 0
(d) if A -> B and B -> A then A = B
(e) if A -> B and B -> C then A -> C
(f) A -> A

which effectively serves as an alternate definition.

When you carry out a reduction of a state Q, to derive a word w in the
language, you're actually writing down a series of inequalities to prove that
Q -> w. For example, with the finite automaton S4

Q0 = 1 + a Q1 + b Q0 (S4)
Q1 = 1 + a Q2 + b Q3
Q2 = a Q3 + b Q2
Q3 = 1 + a Q3 + b Q3

you have the following derivation:

Q0 -> a Q1 -> a a Q2 -> a a a Q3 -> a a a 1 = a a a

thus, Q0 -> a a a.

A consequence of this definition is the following property:

E = { w in X*: E -> w }

that is, every regular expression is equal to the set of words derived
from it.

(1.9) Infinite Automata and Recursive Systems of Equations
Suppose you attempt to treat the following set as a regular expression
and factor it:

S = { a^n b^n: n >= 0 }.

This set is effectively an infinite regular expression given by the
following recursive equation:

S = 1 + a b + a a b b + a a a b b b + ...
= 1 + a (1 + a b + a a b b + ... ) b
= 1 + a S b

If you attempt to construct a DFA for it, you will end up with an
infinite number of states. In fact, we'll do that. Define the following
classes of expressions:

S(n) = S b^n n >= 0
T(n) = b^n

Then the following holds:

\T(0) = 1
\T(n) = 0, if n > 0
dT(0) = 0
dT(n) = b T(n - 1) if n > 0

\S(n) = \S \b^n = \(1 + a S b) \T(n) = 1 \T(n)
= \T(n)
dS(n) = dS b^n + d(b^n)
= a S b b^n + dT(n)
= a S(n + 1) + dT(n)

This results in the following infinite system:

S(0) = 1 + a S(1)
S(n) = b T(n - 1) + a S(n + 1) if n > 0
T(0) = 1
T(n) = b T(n - 1), if n > 0

This represents the infinite automaton:

[[S(0)]]
| a
v b
S(1) ---------> [[T(0)]]
| a ^
v b | b
S(2) ---------> T(1)
| a ^
v b | b
S(3) ---------> T(2)
| a ^
v b | b
... ...

It's easy to show this is minimal. The only possible equivalent states
here are (apart from equality):

S(n) = S(n'), 0 < n < n'
T(n) = T(n'), 0 < n < n'

Let N be the smallest integer, n, such that either of the equivalences
above holds. If
S(N) = S(n'),
then
b T(N) + a S(N+1) = b T(n') + a S(n'+1),
and thus
T(N) = T(n').

If
T(N) = T(n')
then
b T(N-1) = b T(n'-1).
Thus
T(N-1) = T(n'-1),

which is impossible by assumption.

Several times in previous articles, the link between formal languages
and quantum theory has been discussed. In the discussion above it actually
looks like we're talking about quantum states, energy levels, and operators.
The states S(0) and T(0) look like ground states, the transition

S(n) -> a S(n + 1)
T(n) -> b T(n - 1)

respectively like the absorption and emission of a quantum of energy. There
may even be a way to relate Feynmann Diagrams to automata, following the
developments of the article "The Formal Language Representation of Algebras".

The context free algebra embodied some of this analogy by the use of the
Dirac bra and ket operators. An expression, in fact, corresponding to
this infinite automaton can be written as:

<0| (<1| a)* (b |1>)* |0>

which provides a closed solution to the recursive equation S = 1 + a S b.
Also, the <n|'s look like Creation operators, and the |n>'s like Anhilliation
operators.

The relations that are used to define the context free algebra can then be
used to derive any of the words a^n b^n. For instance:

<0| (<1| a)* (b |1>)* |0>
-> <0| (<1| a) (b |1>) |0>
= <0| <1| |1> |0> a b
= <0| |0> a b
= a b
and
<0| (<1| a)* (b |1>)* |0>
-> <0| (<1| a) |0> = <0| <1| |0> a = <0| 0 a = 0

These expressions are the generalization of regular expressions that were
discussed previously: the Context Free Expressions.