Semi-discrete context-free languages^†

^†This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant A7877

Abstract

A language L over a finite alphabet is said to be semi-discrete if there exists a positive integer k such that L contains at most k words of any given length. If k=1, the language is said to be discrete. It is shown that a language is semi-discrete and context-free iff it is a discrete union of languages of the form , iff it is a finite disjoint union of discrete context-free languages. Closure properties and decision problems are studied for the class of semi-discrete context-free languages

Keywords:

• Language
• discrete
• semi-discrete
• context-free
• regular
• iterative pairs
• decidable

C.R. Categories:

• F.4.3

^†This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant A7877

^†This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant A7877

Notes

^†This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant A7877