A language is regular if it can be recognized by a finite automaton. According to the pumping lemma, every infinite regular language contains a regular subset of the form uv(+)w, where u, v, w are words and v is not empty. It is known that every regular language can be expressed as (boolean ORiis an element of1 u(i)v(i)(+)w(i)) boolean OR F, where I is an index set, u(i), w(i) is an element of A*, v(i) is an element of A(+), i is an element of I and F is a finite set of words over the alphabet A. This expression is called a regular component decomposition of the language. A language is called regular component splittable if it can be expressed as a disjoint union of regular components and a finite set. A language which has a regular component decomposition with finite index is called a finite regular component representable language. It has been shown that every finite regular component representable language is regular component splittable by Shyr and Yu in (Discrete Appl. Math. 82 (1998) 219). They conjectured that every regular language is regular component splittable in (Acta Math. Hung. 78(3) (1998) 251). The conjecture is proved in this paper. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 5]
展开▼
