Please use this identifier to cite or link to this item:
標題: The single loop representations of regular languages
作者: Shyr, H.J.
Yu, S.S.
關鍵字: formal language;context-free language;regular language;single loop;semi-discrete;discrete
Project: Discrete Applied Mathematics
期刊/報告no:: Discrete Applied Mathematics, Volume 82, Issue 1-3, Page(s) 219-229.
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.
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)86751-0
Appears in Collections:期刊論文

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.