Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/study/courses/avtomat.pdf Дата изменения: Sat Sep 7 21:07:19 2013 Дата индексирования: Thu Feb 27 21:21:38 2014 Кодировка: Windows-1251

Программа спецкурса "Теория автоматов"
Теория автоматов представляет собой раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации. В программу курса вошли классические результаты из таких разделов, как диагностика и расшифровка автоматов, языки описания поведения автоматов, синтез автоматов, поведение автоматов в геометрических средах. 1. Понятие автомата. Конечные и бесконечные автоматы. Функционирование конечного автомата. Основные способы задания конечного автомата: таблица, диаграмма Мура, канонические уравнения. Конечно-автоматные функции. 2. Обобщения понятия автомата: недетерминированные, частичные, асинхронные автоматы. Вероятностные автоматы. Автоматы над термами. 3. Детерминированные функции. Информационные деревья. Остаточные функции детерминированной функции. Ограниченно - детерминированные функции. Вес о.-д. функции. 4. Преобразование периодических последовательностей ограниченно - детерминированными функциями. 5. Неотличимость состояний конечного автомата. Автомат приведенного вида. Неотличимость и изоморфизм конечных автоматов. Теорема о существовании единственного с точностью до изоморфизма автомата приведенного вида в классе K (A, B ), неотличимого от заданного автомата. Пример автомата приведенного вида, не имеющего одного слова, отличающего любые два его состояния. 6. Слабая неотличимость автоматов. Различие отношений неотличимости и слабой неотличимости. Счетность множества классов отношения слабой неотличимости. 7. Достижимость состояний. Сильно связные автоматы. Совпадение отношений неотличимости и слабой неотличимости для класса сильно связных автоматов. 8. Понятие r - неотличимости конечных автоматов. Теорема о существовании для любого натурального r двух автоматов, являющихся r - неотличимыми, но не r + 1 - неотличимыми. 9. Неотличимость двух состояний множеством слов. Лемма о разбиениях множества состояний автомата на классы неотличимости множествами M и M AM . Построение множества, отличающего любые два состояния автомата, на основе некоторого исходного множества слов M . 10. Теорема Мура о длине слова, отличающего два состояния конечного автомата. Длина слова, отличающего два состояния различных автоматов. Примеры, устанавливающие неулучшаемость этих оценок длины. 11. Базис достижимости и базис отличимости для конечного автомата. Леммы о существовании этих базисов.

1


12. Построение множества слов, отличающего заданный инициальный автомат приведенного вида от любого другого инициального автомата приведенного вида, имеющего не более n состояний (с помощью базисов отличимости и достижимости). 13. Кратные эксперименты с конечными автоматами. Безусловные и условные кратные эксперименты. Результат применения кратного эксперимента к автомату. Длина, кратность и объем результата. Диагностические и тестовые кратные эксперименты. Простейшие оценки длины кратных диагностических экспериментов. 14. Алгоритм нахождения диагностического кратного безусловного эксперимента, имеющего наименьший объем. 15. Простые эксперименты с конечными автоматами. Безусловные и условные простые эксперименты. Результат применения эксперимента к автомату. Диагностические и тестовые простые эксперименты. Утверждений об отсутствии в общем случае тестового простого эксперимента для инициального автомата в классе автоматов, отличающихся от него выбором начального состояния. 16. Установочные эксперименты для конечного автомата. Теорема Мура - Карацубы. 17. События, представимые в конечном автомате. Операции над событиями. Регулярные события. Лемма о решении простейшего уравнения для событий. Лемма о решении системы уравнений с регулярными коэффициентами. 18. Регулярность событий, представимых в конечном автомате. 19. Обобщенные источники. Событие, определяемое обобщенным источником. Существование обобщенного источника, определяющего регулярное событие. Представимость события, определяемого обобщенным исотчником. Теорема Клини. Пример нерегулярного события. 20. Обычный источник. Задание регулярных событий источниками. Теорема Лупанова о числе состояний автомата, необходимом в худшем случае для представления события, определяемого n - вершинным источником. 21. Регулярные выражения. Регулярность пересечения, разности и дополнения регулярного события. Регулярность проекции регулярного события. Регулярность события, образованного словами, все начала которых принадлежат заданному регулярному событию. 22. Сверхслова и сверхсобытия. Сверхсобытия, представимые в конечном автомате с помощью заданного семейства подмножеств выходного алфавита. Операции над сверхсобытиями. Общерегулярные сверхсобытия. Лемма о регулярности множества слов, переводящих автомат из заданного состояния в него же и определяющих заданную группу выходных символов. 23. Общерегулярность представимых сверхсобытий. 24. Сверхисточники и определяемые ими сверхсобытия. Существование сверхисточника, определяющего заданное общерегулярное сверхсобытие. 2


25. Представимость сверхсобытия, определяемого сверхисточником. Теорема МакНотона. 26. Пример необщерегулярного сверхсобытия. 27. Автоматы в лабиринтах. Формулировка теоремы Будаха и схема ее доказательства.

Литература
1. В.Б.Кудрявцев, С.В. Алешин, А.С.Подколзин. Введение в теорию автоматов. М., "Наука", 1985. 2. В.Б.Кудрявцев, С.В. Алешин, А.С. Подколзин. Элементы теории автоматов. М., изд-во МГУ, 1978.

3