The Untold Story of Formal Language Theory
Mark Hopkins
formal languages that I've been working on for the last several years and
which has only surfaced from time to time over the USENET. Given time, I
may turn this into a series since the developments are extremely wide-ranging,
and diverse.
To make a long story short, this approach originated in my studies of
parsing theory in an effort to try and develop better methods of implementing
a particular parsing method (LR(k)). However, at one juncture I made a
fateful decision to step back and redo everything from a purely algebraic
approach. Subsequent developments far transcended this context.
It is my contention that if formal languages had been unknown up to now
and were (re)discovered today, that the result would essentially be an
algebraic formulation which extends to theory of regular expressions and
finite automata to cover more general classes of languages and transducers.
For the longest time, the perception was that the only way to come up with
such an algebra was to extend the operator set (concatenation A, B |-> AB,
union A, B |-> A + B, and Kleene Star A |-> A*), for instance invoking a
substitution operator or a "least fixed point" operator. Then you could
arrive at a notion of Context Free Expressions, Push Down Transductions,
Turing Expressions and so on.
This perception is wrong. What needed to be changed was not the operator
set, but the underlying algebra. In particular, when you take rational
subsets of a free monoid, you get only the regular languages. But what if
you take rational subsets of an monoid that is not free?
Indeed, every language (computeable or not) can be represented as a
rational subset of a monoid. In particular, let L be a language over an
alphabet X. Since L is countable, we can represent it as follows:
L = { w0, w1, w2, ... }
So consider the monoid generated by X union { o, p, q }, where o, p and q
are auxillary symbols not in X, and subject to the relations:
p o^n q = wn, for n = 0, 1, 2, ...
Then L is the rational subset p o* q. Even more, the entire algebra of
rational subsets over X is freely embedded in the algebra of rational
subsets of this new monoid.
We can do this for any countable language in general.
Even entire language families could be embedded in this way. Consider
the set T(X) of turing computeable languages over a finite alphabet X.
It too is countable so let w_m_n stand for the nth word in the mth language
of T(X), assuming an enumeration of languages in T(X) and enumeration for
each language. Then we can form a *single* monoid in which *every* one of
these languages is a rational subset. This time we use 4 extra symbols,
p, o, q and O, and impose the relations p O^m o^n q = w_m_n. Then if
we call the mth language of T(X) L_m, we have that L_m = p O^m o* q --
a rational subset.
Of course, all that's overkill. The trick is to do the same, but making
the monoid be finitely generated AND with a finite set of relations. All
you have to do to get that is simply encode a Turing Machine -- this is
basically a statement of the Higman Embedding Theorem.
Now is there a way to characterize the algebras corresponding to rational
subsets of monoids in the abstract? Well, it turns out there are several
highly useful ways to do this, all giving you equational oompleteness with
respect to the regular expressions. The one I'll treat here today is the
Rational Monoid.
First, we'll need a few definitions. I assume everyone knows what a
monoid is (a set with an associative product and an identity, usually
denoted respectively by a, b |-> ab and 1 in this presentation). Then
you have:
DEF 1: The rational subsets R(M) of a monoid M is the smallest family of
subsets of M such that:
(1) {} is in R(M)
(2) {w} is in R(M) for each w in M
(3) if A, B are in R(M) then so are AB, A+B and A*.
where AB is the set { ab: a in A, b in B }, A+B is the union of A and B,
and A* is the union 1 + A + AA + AAA + AAAA + ...
DEF 2: A Rational Monoid is a partially ordered monoid in which the
least upper bound is a homomorphism from the rational subsets of the
monoid to the monoid. In particular, you have the following:
lub( {x} ) = x --- or: lub commutes with the monoid embedding
x |-> {x}.
lub(AB) = lub(A) lub(B)
A question you may be asking is whether this characterizes the lub operator
in the abstract. The answer is no. However, you can formulate an equivalent
definition:
THEOREM 1: Equivalent definition of rational monoid
Let M be a monoid and f: R(M) -> M be a monoid homomorphism.
Impose the following conditions on f:
(1) f({x}) = x
(2) f(AB) = f(A) f(B)
(3) f(union R) = f( { f(A): A is in R } )
where A, B are in R(M), and R is a subset of R(M) such that
union R is in R(M).
I actually prefer the latter definition since it's something you can
generalise to Categories, if you think of a monoid as being a single-object
category. In fact, this is how you would do it.
DEF: Let C be a category, and C(A, B) denote the set of morphisms from A
to B, where A, B are objects in C. Define R(A, B) as the smallest
family of sets such that:
(1) {} is in R(A, B) for all objects A, B in C.
(2) {f} is in R(A, B) for all morphisms f: A -> B.
(3) If U is in R(A, B) and V is in R(B, C) then
VU = { gf: f in U, g in V } is in R(A, C)
(4) If U is in R(A, A) then U* is in R(A, A), where
U* = { 1_A } + U + UU + UUU + ...
(5) If U, V are in R(A, B) then so is their union U + V.
DEF: A Rational Category is a category with an operator f: R(A, B)->C(A, B)
satisfying analogous conditions (1), (2) and (3) to those listed under
THEOREM 1.
But I digress...
A rational monoid homomorphism (or generally, a rational functor) is
a monoid homomorphism which preserves the least upper bound for all
rational subsets:
DEF 3: Let M, N be rational monoids with f: M -> N a monoid homomorphism.
Then f is a rational monoid homomorphism if f(lub A) = lub(f(A)),
for all A in R(M).
Then you get a bunch of VERY interesting theorems that show off the beauty
of the entire concept:
THEOREM 2: R(M) is a rational monoid for all monoids M.
THEOREM 3: If M is a rational monoid, then lub: R(M) -> M is a rational
monoid homomorphism
THEOREM 4: If f: M -> N is a monoid homomorphism, then the induced
function f: R(M) -> R(N), defined by f(A) = { f(a): a in A }
is a rational monoid homomorphism.
COROLLARY: If M is a rational monoid generated by the set X, then M is
a homomorphic image of R(X) -- the set of regular languages over
X. Even more, this homomorphism is a rational monoid homomorphism.
The last corollary means, in particular, you never need consider anything
more general than rational subsets taken over a FREE monoid. The monoid
relations are "lifted up" into relations over regular expressions.
So in brief, a rational monoid is just an algebra for regular expressions
in which on-trivial relations are allowed.
Now, you can do this for other families of sets besides just R(M). For
instance, consider a monoid M and its family of finite subsets J(M). If
you perform a similar construction
DEF: A "finitary monoid" is a partially ordered monoid in which the least
upper bound operator is a monoid homomorphism from J(M) to M
Then you get a definition for idempotent semi-rings. You could also consider
similar definitions, say with respect to the context free subsets of a monoid
or the computeable subsets of a monoid, and you get new concepts of
"algebraic monoid" and "transcendental monoid", invoking an often used
analogy.
----------------------
Given rational monoids, you can construct new ones in several ways
DEF: Let M be a rational monoid, define Mn(M) to be the rational monoid
of n x n matrices over M.
Note that we define the items 0 = lub {}, a + b = lub { a, b }, and
a* = lub { 1, a, aa, aaa, ... } for arbitrary rational monoids. So we
can do matrix algebra. The matrix product is defined in the usual way,
and partial ordering is defined by
m < n if m[i, j] < n[i, j] for all indices i, j
So we can define m* = lub { 1, m, mm, mmm, ... } and show that indeed this
least upper bound exists.
DEF: Let M, N be rational monoids. Define the "tensor product" M x N as
the rational monoid generated from M and N such that
mn = nm for all m in M, n in N
In particular, M x N has the Universal Property:
THEOREM: If f: M -> P, and g: N -> P are rational monoid homomorphisms with
f(m) g(n) = g(n) f(m), then there is a unique extension, h:MxN->P
such that h(m) = f(m), for m in M, and h(n) = g(n) for n in N.
where the inclusion maps M -> MxN and N -> MxN are omitted for brevity.
These are, then, some examples of rational monoids
R(X) -- the family of regular languages over alphabet X.
R(X, Y) -- the rational transductions over X and Y -- R(X,Y)=R(X)xR(Y).
C(X) -- the context-free languages over alphabet X.
C(X, Y) -- the push-down transductions over X and Y
T(X) -- the turing languages over X
L(X) -- the class of all subsets over the free monoid generated by X
M(X) -- the countable-dimensional infinite matrix algebra over L(X)
(if you thought L(X) was big, take a look at M(X)!)
C2 --- the rational monoid generated from { b, d, p, q } by the relations
bd = pq = 1, bq = pd = 0, db + qp = 1
An interesting property of C2 is that it is isomorphism to all of its
finite dimensional matrix algebras. In particular, there is the rational
monoid isomorphism C2 <--> M2(C2) given by the correspondence:
A B <--> d A b + d B p + q C b + q D p
C D
Another interesting property that holds of C2 is that:
THEOREM: If M is a rational monoid, then the rational monoid C(M) of
context free subsets of M can be embedded within C2 x M.
THEOREM: If M is a rational monoid, then the turing subsets T(M) of
M can be embedded within C2 x C2 x M.
-- which leads, respectively, to the notions of Context Free Expressions,
and Turing Expressions.
THEOREM: C2 can be represented as a subalgebra of M({}) by the following:
b = matrix with i-2i component 1, all other components 0
p = matrix with i-(2i+1) component 1, all others 0
d = transpost of b, q transpose of p.
And it's here we'll take up our story next.