birmaga.ru
добавить свой файл

1
Программа курса «Теория автоматов»


(специальности КН, КБ, 3 семестр, 2010 г.)


  1. Понятие об автомате (ДКА): черный ящик, алгебра, помеченный орграф. Распознавание слов и языков при помощи ДКА. Полный и неполный ДКА. НКА как алгебра и орграф. Распознавание при помощи НКА. Реализация вычисления в НКА.

  2. НКА и ДКА: теорема Рабина-Скотта. Алгоритм детерминирования. Лямбда-НКА, их эквивалентность ДКА и алгоритм детерминирования.

  3. Эквивалентность состояний и эквивалентность ДКА. Изоморфизм ДКА. Приведенные ДКА. Теорема существования, единственности и минимальности приведенного ДКА. Алгоритм построения приведенного ДКА, доказательство корректности.

  4. Операции над языками. Регулярные языки и регулярные выражения. Теорема Клини. Замкнутость класса регулярных языков относительно дополнения, пересечения, разности.

  5. Построение автомата по регулярному выражению (лямбда-НКА, детерминирование, минимизация). Уравнение L=U+LV. Построение регулярного выражения по автомату: составление системы линейных уравнений и ее решение методом Гаусса.

  6. (Левые) частные языка. Критерий регулярности в терминах частных. Связь частных и минимального автомата (теорема Майхилла-Нероуда). Критерий регулярности в терминах правых конгруенций.

  7. Моноид переходов автомата. Распознавание языков моноидами, критерий регулярности. Синтаксический моноид языка, критерий регулярности.

  8. Замкнутость класса регулярных языков относительно операций (реверс, морфизмы, деление, замыкания относительно префиксов, суффиксов, подслов), построение соответствующих автоматов. Разрешимость алгоритмических проблем о регулярных языках: вхождение, пустота, эквивалентность, включение.

  9. Автомат Ахо-Корасик для поиска по шаблону и по множеству шаблонов. Функция отката и эффективное построение автомата А-К. Применение автомата А-К для распознавания языков с конечным антисловарем, применение для сжатия данных.
  10. Дескриптивная сложность регулярных языков. Сложность операций: объединение, пересечение, произведение, итерация.


  11. Синхронизируемые автоматы. Проверка синхронизируемости. Кубическая оценка длины кратчайшего синхронизирующего слова. Гипотеза Черни.

  12. Конечные автоматы и бесконечные слова. Детерминированные и недетерминированные автоматы Бюхи. Автоматы Мюллера. ω-регулярные языки, замкнутость относительно операций, характеризация.

  13. Автоматы с выходом. Представление разбиения свободного моноида на регулярные языки автоматом с выходом. Конечные преобразователи, примеры. Рациональные отношения. Теорема Нивата.

  14. Клеточные автоматы. Конфигурации. Эволюция. Сады Эдема, промежуточные и предельные конфигурации.