О числовых характеристиках формальных языков

Рассмотрена задача подсчета числа слов регулярного языка заданного состава. Задан алфавит из символов. Состав слова определен как вектор. Введены функции числа слов заданного состава. Определены простые оценки указанных функций для языков, полученных из языков с помощью обычных операций (объединение, конкатенация, итерация). Изучены ряды для языков, порожденных автоматами.

Литература

[1] Гончаров В.Л. Из области комбинаторики // Известия АН СССР. Сер. матем. 1944. Т. 8. Вып. 1. С. 3-48.

[2] Коршунов А.Д. Об асимптотике числа бинарных слов с заданной длиной максимальной серии I // Дискретный анализ и исследование операций. 1997. Т. 4. № 4. С. 13-46.

[3] Косточка А.В., Мазуров В.Д., Савельев Л.Я. Число q-ичных слов с ограничением на длину максимальной серии // Дискретная математика. 1998. Т. 10. Вып. 1. С. 10-19. DOI: https://doi.org/10.4213/dm413

[4] Хомский М., Миллер Д. Языки с конечным числом состояний // Сер. Киб. сборник. Вып. 4. М.: ИЛ, 1962. С. 233-255.

[5] Строгалов А.С. О регулярных языках с полиномиальным ростом числа слов // Дискретная математика. 1990. Т. 2. Вып. 3. С. 145-152.

[6] Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. 744 с.

[7] Трахтенброт Б.А., Бардзин Я.М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. 400 с.

[8] Мотвани Р., Ульман Дж., Хопкрофт Дж. Введение в теорию автоматов, языков и вычислений. М.-СПб.-Киев: Вильямс, 2002. 528 с.

[9] Архипов Г.И., Садовничий В.А., Чубариков В.Н. Лекции по математическому анализу. М.: Дрофа, 2003. 640 с.

[10] Копсон Э. Асимптотические разложения. М.: Мир, 1966. 160 с.

[11] Адельсон-Вельский Г.М., Кузнецов О.П. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с.

[12] Федорюк М.В. Асимптотика, интегралы и ряды. М.: Наука, 1987. 544 с.