Formal languages over free binoids

摘要

We introduce new algebraic systems named bisemigroups, bimonoids and binoids. A bisemigroup consists of a set of objects and two associative operations. A bimonoid is a bisemigroup which has an identity to each operation. A binoid is a bimonoid in which the two identities coincide. In accordance with the well known hierarchy of formal grammars over free monoids, we shall introduce five types of grammars for defining formal languages over free binoids, and present many basic properties of these languages. Especially we present several relations between these languages and Turing machines and finite automata.