Перейти к полному списку специальных курсов кафедры

Программа экзамена по спецкурсу "Теория автоматов"

Программа курса, 2013 г.

1. Понятие конечного автомата, основные определения. Обобщения понятия конечного автомата. Примеры автоматов, описывающих сложение n-разрядных чисел и деление n-разрядных чисел на фиксированное число. Способы задания автомата, канонические уравнения, диаграмма Мура.

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, Наука, Москва.

Наверх