Please use this identifier to cite or link to this item:
|標題:||The single loop representations of regular languages||作者:||Shyr, H.J.
|關鍵字:||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.
|Appears in Collections:||期刊論文|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.