Re: A tortoise-rambling email

On Wed, Sep 11, 2002 at 03:40:08AM -0700, Greg Allen wrote:
> To tediously refine the algorithm classfication further then, we could have,
> "bottom-up (marked)" and "bottom-up (unmarked)". Presumably the "marking" is
> what makes it a "transducer"?

No, no, a (finite-state) transducer is just a mathematical device that
recognizes regular relations, just like a finite-state automaton recognizes
regular languages. Transducers can be used to parse context-free languages by
transforming its input until a fixed-point is reached, that is, no more
transformations are possible. In perl, this translates to the construct

	1 while s/.../.../;

Marking of the parts that were already done is just a way to reach a fixed-
point.

pom