𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Regular component decomposition of regular languages

✍ Scribed by Y.J. Liu

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
198 KB
Volume
299
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

A language is regular if it can be recognized by a ΓΏnite automaton. According to the pumping lemma, every inΓΏnite 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 ( i∈I uiv + i wi) βˆͺ F, where I is an index set, ui; wi ∈ A * ; vi ∈ A + ; i ∈ I and F is a ΓΏnite 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 ΓΏnite set. A language which has a regular component decomposition with ΓΏnite index is called a ΓΏnite regular component representable language. It has been shown that every ΓΏnite 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.

πŸ“œ SIMILAR VOLUMES

Squares of regular languages
Squares of regular languages
✍ Gerhard Lischke πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties.

Regular binoid expressions and regular b
Regular binoid expressions and regular binoid languages
✍ Kosaburo Hashiguchi; Yoshito Wada; Shuji Jimbo πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 285 KB

A bisemigroup consists of a set of elements and two associative operations. A bimonoid is a bisemigroup which has an identity to each associative operation. A binoid is a bimonoid which has the same identity to the two associative operations. In a previous paper, we introduced these three notions, a

Learning approximately regular languages
Learning approximately regular languages with reversible languages
✍ Satoshi Kobayashi; Takashi Yokomori πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 490 KB

In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data