Regular component splittable languages
type: Item
instance of: scholarly article
title: Regular component splittable languages
zbMATH Open document ID: 0905.68084
DOI: 10.1023/A:1006586923902
author: H. J. Shyr
author: Shyr-Shen Yu
published in: Acta Mathematica Hungarica
publication date: 1998-11-24T00:00:00Z
review text: 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.
reviewed by: Frank Drewes
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1226460
zbMATH Keywords: regular language
zbMATH Keywords: context-free language
zbMATH Keywords: decomposition
zbMATH Keywords: regular component
MaRDI profile type: Publication
full work available at URL: a:1006586923902
OpenAlex ID: W1692710806
description: scientific article; zbMATH DE number 1226460