Equality sets of prefix morphisms and regular star languages
We consider equality sets of prefix morphisms, that is, sets E(g(1), g(2)) = {w vertical bar g(1) (w) = g(2)(w)}, where g(1) and g(2) are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form pi(A)(E(g(1), g(2))) for some prefix morphisms g(1) and g(2), and a projection pi(A) which deletes the letters not in A. (c) 2005 Elsevier B.V. All rights reserved.
equality sets star languages regular languages representation formal languages