Аннотация:В кандидатской диссертации [1] была поставлена и решена задача о нахождении
верхней оценки на минимальную длину слов из регулярного языка, склеивающихся
(то есть имеющих совпадающий образ) при алфавитном кодировании (если такая
склейка вообще существует). В рамках данной курсовой работы была поставлена задача о нахождении соответствующих нижних оценок. Для упрощения задачи, было
решено рассмотреть случай, когда регулярные языки имеют линейную функцию роста, а схема кодирования преобразует все буквы входного алфавита в один и тот же
символ. Для такого кодирования образ слова однозначно определяется по его длине.
Удалось получить нижние оценки, совпадающие по порядку с верхними оценками из
кандидатской диссертации для таких языков и такого кодирования. Кроме того, для
этого подслучая удалось уменьшить соответствующую верхнюю оценку.