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

Основной количественной характеристикой языка $L$ над конечным алфавитом $\Sigma$ является комбинаторная сложность – функция $C_L(n)=|L\cap\Sigma^n|$. Мы выражаем тип и параметры асимптотического поведения функции комбинаторной сложности регулярного языка через характеристики конечного автомата и приводим эффективные алгоритмы вычисления этих характеристик. На основе полученных результатов мы описываем колебания комбинаторной сложности для произвольных, префиксных и факториальных регулярных языков.