Newsgroups: sci.math
From: tycchow@cayley.mit.edu (Timothy Y. Chow)
Subject: Illegal manipulation?
Message-ID: <1994May28.184517.13405@galois.mit.edu>
Organization: None. This saves me from writing a disclaimer.
Date: Sat, 28 May 94 18:45:17 GMT
Lines: 56
Some time ago someone posted the following "calculation." Suppose you
have a language L defined by
L = 1 | aL
where "1" denotes the empty word. Now one "illegally" interprets | as
addition and concatenation as multiplication and writes
L - aL = 1
(whatever that means). Continuing, we obtain L(1-a) = 1 or L = 1/(1-a) or
L = 1 | a | aa | aaa | aaaa | ...
which is the "right" answer. At the time I was surprised by this, although
I shouldn't have been, since the basic principle here was actually covered
in a course I took a couple of years ago (in somewhat disguised form). Just
this past week I attended an expository lecture by C. Reutenauer which tore
away the disguise. I thought I'd share my enlightenment with others.
Punchline first: the above idea is the key to Schutzenberger's fundamental
theorem that a noncommutative formal power series is rational if and only
if it is recognizable by a finite automaton (essentially a regular language).
Schutzenberger's theorem builds on Kleene's well-known work.
O.K., what does *that* mean? Well, first fix an alphabet A, and define
a _language_ L to be a subset of words whose letters come from A. Now
we all know that one natural way of manipulating such languages is via
the operations |, Kleene closure *, and concatenation. This is the
"classical" way of proceeding.
On the other hand, one can also represent a language as a noncommutative
formal power series: simply sum up all the words in the language. The
advantage of doing this is that there is nothing to stop us from allowing
the coefficients to lie in some field (say Q) and not just the nonnegative
integers. Once we do this, we can introduce all the usual things associated
with formal power series: ring operations, invertibility, composition, etc.
It is also natural to define a _rational_ series to be one that lies in the
smallest subring that contains the polynomials and which is closed under
taking inverses (when inverses exist).
The fundamental theorem now is that rational series are precisely those
that are recognizable by a finite automaton (where we allow the edge labels
to be any rational multiple of a letter in A). And one of the key ideas
is the "illegal" manipulation above, i.e., the identification of | with
formal power series addition, concatenation with formal power series
multiplication, and Kleene closure with inversion (a^* <-> (1-a)^(-1)).
Thus for example the rational series b (1-ab)^(-1) (a + b) can also be
represented by the regular expression b (ab)^* (a | b).
So the "illegal" manipulation turns out to be not so illegitimate after all!
--
Tim Chow tycchow@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949