Regular component splittable languages (Q1272195)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Regular component splittable languages
scientific article

    Statements

    Regular component splittable languages (English)
    0 references
    0 references
    0 references
    24 November 1998
    0 references
    The authors study the problem of decomposing regular and context-free languages into regular components, where a regular component is a language of the form \(uv^+w\) \((u,w\in X^*\), \(v\in X^+\) for some alphabet \(X\)). A language is called (finitely) regular component splittable if it is a (finite) disjoint union of regular components and a finite language. It is shown that all regular languages of the form \((uv^+w)^+\) and those of the form \(uv^+wx^+y\) are regular component splittable. Moreover, the cases are characterized in which these languages are even finitely regular component splittable. The authors conjecture that, in fact, all regular languages are regular component splittable. As for context-free languages, it is shown that the Dyck language and the balanced language (both over a two-letter alphabet) are regular component splittable. Furthermore, each of the so-called abelian-generated normal disjunctive context-free languages is regular component splittable. Finally, the authors construct an infinite context-free language having no infinite regular subset. Consequently, this language constitutes an example of a context-free language which is not regular component splittable.
    0 references
    0 references
    0 references
    regular language
    0 references
    context-free language
    0 references
    decomposition
    0 references
    regular component
    0 references
    0 references