Личный кабинет
Подробное описание документа
Belousov A. I.
On Certain Classes of Irregular Languages / Belousov A. I., Ismagilov R. S., Filippova L. E. - URL: https://vestniken.bmstu.ru/catalog/math/compmath/924.html (дата обращения: 11.03.2026). - DOI 10.18698/1812-3368-2020-3-30-43 // Вестник МГТУ им. Н. Э. Баумана. Сер. Естественные науки. - 2020. - № 3. -
Скачать документ
Objective of this paper is to prove certain regularity and irregularity conditions in languages determined by a set of integer vectors called distribution vectors of the number of letters in words over a finite alphabet. Each language over the finite alphabet uniquely determines its proprietary set of distribution vectors and vice versa, i.e., each set of vectors is associated with a language having this set of distribution vectors. A single necessary condition for the language regularity was considered associated with the concept of Z+-plane (sets of points with non-negative integer coordinates lying on a plane in the affine space). The condition is that a set of distribution vectors determined by any regular language could be represented as a finite union of the Z+-planes. Certain sufficient irregularity conditions associated with the distribution vector properties were proven. Based on this, classes of irregular languages could be identified. These classes are determined by a set of vectors (points) that could not be represented as a finite union of the Z+-planes; by a set of vectors containing vectors with arbitrarily high values of each coordinate and having certain restrictions on the difference between maximum and minimum values of the coordinates; by a set of vectors called the sparse sets. A method is proposed for building such sets using strictly convex and strictly increasing numerical sequences. These sufficient irregularity conditions are based on the Myhill — Nerode theorem, which is known in the formal languages' theory. Examples of applying the proved theorems to the analysis of languages' regularity/irregularity are presented
519.76 Математические вопросы семиотики
Статья опубликована в следующих изданиях
№ 3. - 2020.
