Density of grammar forms part II

Abstract

In the second part of this paper we give two characterizations for dense intervals consisting of grammatical families. By means of the characterizations it is proved that denseness is undecidable for context-free forms. On the other hand, denseness turns out to be decidable if the two languages, generated by the forms that define the interval in question, are known to be regular.

The characterization theorems also enable us to investigate the maximality of dense intervals. We demonstrate that every such interval containing families with infinite languages can be extended from below while retaining density.

The notion of a language form is used as a basic auxiliary concept in our argumentation.

Keywords:

• Grammar forms
• density
• L forms

C.R. Categories:

• 5.23
• F.4.2
• F.4.3