О вычислении размаха регулярных языков при алфавитном кодировании

Аннотация

В данной работе вводится и изучается понятие размаха регулярных языков при алфавитном кодировании. Основным результатом является ранее не известное свойство дихотомии единичного и бесконечного размахов для языков специального итерационно-конкатанированного вида в случае двухэлементного входного алфавита. Также показано, как для такого алфавита на основании этого результата можно построить новый алгоритм вычисления размаха регулярного языка в общем случае (сама алгоритмическая разрешимость этого вычисления является известным фактом).

Ключевые слова: регулярный язык, алфавитное кодирование, размах.

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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover