The dissecting power of regular languages

A recent study on structural properties of regular and context-free languages has greatly promoted our basic understandings of the complex behaviors of those languages. We continue the study to examine how regular languages behave when they need to cut numerous infinite languages. A particular interest rests on a situation in which a regular language needs to “dissect” a given infinite language into two subsets of infinite size. Every context-free language is dissected by carefully chosen regular languages (or it is REG-dissectible). In a larger picture, we show that constantly-growing languages and semi-linear languages are REG-dissectible. Under certain natural conditions, complements and finite intersections of semi-linear languages also become REG-dissectible. Restricted to bounded languages, the intersections of finitely many context-free languages and, more surprisingly, the entire Boolean hierarchy over bounded context-free languages are REG-dissectible. As an immediate application of the REG-dissectibility, we show another structural property, in which an appropriate bounded context-free language can “separate with infinite margins” two given nested infinite bounded context-free languages.

► The notions of dissectibility and i-separation are introduced to analyze the structural behaviors of formal languages.
► Every infinite recursive language is P-dissectible and every infinite language is REG/nREG/n-dissectible.
► There are infinite languages in the log-space class L that are not REG-dissectible.
► Every language in the Boolean hierarchy over bounded context-free languages is REG-dissectible.
► A certain language in the Boolean hierarchy can i-separate every i-covering pair of bounded context-free languages.