The single loop representations of regular languages

✍ Scribed by H.J. Shyr; S.S. Yu

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 782 KB
• Volume: 82
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)86751-0

✦ Synopsis

A regular language of the form UP' M' is called a single loop from the viewpoint of automata theory. It is known that every regular language can be expressed as (U,,,, U,L.;IV, )U F. where .4 is an index set, u,, ~1~ EX*, c, EX~, i E A, 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. WC 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+ c-, the non-fs-representable languages and codes are investigated for their own interests. We show that for u, u t X ' . ~1' I.

being a code implies that it is not an fs-representable language.