Let R be a semiring and A a finite alphabet.
A non-commutative polynomial over A is a finite formal sum of words over A. They form a semiring .
A formal series is a R-valued function c, on the free monoid A*, which may be written as
The set of formal series is denoted and becomes a semiring under the operations
A non-commutative polynomial thus corresponds to a function c on A* of finite support.
In the case when R is a ring, then this is the Magnus ring over R.[1]
If L is a language over A, regarded as a subset of A* we can form the characteristic series of L as the formal series
corresponding to the characteristic function of L.
In one can define an operation of iteration expressed as
and formalised as
The rational operations are the addition and multiplication of formal series, together with iteration.
A rational series is a formal series obtained by rational operations from