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