The single loop representations of regular languages

Abstract

A regular language of the form u upsilon(+)w is called a single loop from the viewpoint of automata theory. It is known that every regular language call be expressed as (boolean ORi epsilon Lambda u(i) upsilon(+)w(i))boolean OR F, where Lambda is an index set, u(i), w(i) is an element of X*, upsilon(i) is an element of X+, i is an element of Lambda, and F is a finite set of words. This expression is called an s-representation of that language. An s-representation is called disjoint if the union of it is disjoint. A language which has an s-representation with finite index is called an fs-representable language. This kind of languages is shown to be the semi-discrete languages. In this paper we give a classification of regular languages by the concept of single loops. We show that every fs-representable language can be expressed as a disjoint s-representation with finite index. We also show that the intersection of an fs-representable language with any context-free language is regular. The relationships between the languages of the form u(+)upsilon(+), the non-fs-representable languages and codes are investigated for their own interests. We show that for u, upsilon is an element of X+, u(+)upsilon(-) being a code implies that it is not an fs-representable language. (C) 1998 Elsevier Science B.V. All rights reserved.