О вычислении размаха регулярных языков при алфавитном кодировании
Получена: 02.11.2026 Доработана: 03.11.2026 Принята: 04.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 258–261
Аннотация
В данной работе вводится и изучается понятие размаха регулярных языков при алфавитном кодировании. Основным результатом является ранее не известное свойство дихотомии единичного и бесконечного размахов для языков специального итерационно-конкатанированного вида в случае двухэлементного входного алфавита. Также показано, как для такого алфавита на основании этого результата можно построить новый алгоритм вычисления размаха регулярного языка в общем случае (сама алгоритмическая разрешимость этого вычисления является известным фактом).
Ключевые слова: регулярный язык, алфавитное кодирование, размах.
BibTeX
@article{IS-Dergach2026,
author = {Дергач, Петр Сергеевич},
title = {{О вычислении размаха регулярных языков при алфавитном кодировании}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {258--261},
}
AMSBIB
\RBibitem{IS-Dergach2026}
\by П.\,С.~Дергач
\paper О вычислении размаха регулярных языков при алфавитном кодировании
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 258--261
EN