Программа курса:

1. Понятие конечного автомата, основные определения. Способы задания автомата, канонические уравнения, диаграмма Мура.
2. Автоматная функция. Детерминированная функция, понятие о.д.-функции. Эквивалентность состояний автомата. Изоморфизм автоматов, приведенный автомат. Теорема о единственности приведенного автомата, эквивалентного данному.
3. Абстрактные автоматы. Проверка эквивалентности состояний автомата.
4. Структурные автоматы, операции суперпозиции и композиции. Схемы в базисе из булевых функций и "задержки". Оператор замыкания. Проблема полноты и выразимости. Мощность полных систем автоматов.
5. Автономные автоматы, проблема полноты и выразимости для автономных автоматов.
6. Полугруппа автомата, связь операций над автоматами с операциями над их полугруппами. Понятие подавтомата и гомоморфного образа автомата. Вербальные операции над автоматами.
7. Системы автоматов с ограниченным числом входов. Полнота системы двухместных автоматов.
8. Линейные автоматы. Проблема полноты для линейных автоматов относительно суперпозиции.
9. Алгоритмическая неразрешимость проблемы полноты конечных систем автоматов относительно композиции.
10. О мощности множества предполных классов автоматов.
11. Системы автоматов, содержащие истинностные функции. Разрешимость проблемы полноты для систем автоматов, содержащих истинностные функции.
12. Классификация замкнутых классов булевых функций по их способности в качестве добавки гарантировать разрешимость задачи полноты.

Литература.
1. Кудрявцев В.Б., Алешин С.В.,Подколзин А.С. "Введение в теорию конечных автоматов".- М.: Наука, 1985 г.
2. Яблонский С.В. Введение в дискретную математику.-М.: Наука, 1985 г.
3. Автоматы, Сборник статей под редакцией Маккарти и Шеннона, ИЛ, Москва, 1956
4. Кудрявцев В.Б., О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами, ДАН СССР т.151,N3,1963, c.493-496.
5. Бабин Д.Н., Вербальные подавтоматы и задача полноты, Вестник МГУ, Математика и механика, 1985, N 3, с.82-85.
6. Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.
7. Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992, выпуск 4, с.41-56, Наука, Москва.
8. Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.

Наверх