A Categorical Framework for Syntactic Semigroups and Language Transformations

Abstract

For a regular language over a finite alphabet we at tach its syntactic recognizer and place such recognizers in a category whose morphisms encode semigroup homomor phisms together with transformations of free semigroups. The main theorem states that the syntactic recognizer of a regular language is a terminal object in the category of all finite semigroup recognizers of that language over the same alphabet. From this we derive minimality and unique ness. We then construct a pullback recognizer associated with every morphism of free semigroups and prove the existence of canonical semigroup homomorphisms induced bylanguage preimages. A new theorem gives a necessary and sufficient criterion for this canonical quotient to be an iso morphism, namely the reflection of syntactic congruence through the free-semigroup morphism. The development is purely semigroup-theoretic and categorical