Regular Component Splittable Languages |
| |
Authors: | H J Shyr S S Yu |
| |
Institution: | (1) Department of Applied Mathematics, National Chung-Hsing University, Taichung, Taiwan |
| |
Abstract: | Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|