Краткие лекции по теории автоматов

Отличный краткий конспект лекций по предмету "теория автоматов" в Pdf-файле.

Содержание лекции

Синтез цифровых автоматов для реализации алгоритмов двоичной арифметики

• Общие сведения о цифровых автоматах. Модель Глушкова. Синтез операционных автоматов
• Пример синтеза операционного автомата для выполнения косвенного умножения беззнаковых чисел
• Виды управляющих автоматов. Структуры автоматов Мили и Мура.
• Пример синтеза управляющего автомата с жесткой логикой (УАЖЛ) для алгоритма умножения беззнаковых чисел в прямом коде

Вопросы из первого раздела для самоконтроля:

• Опишите модель дикретного преобразователя Глушкова.
• Каково назначение Операционного Автомата (ОА) ?
• Роль информационных и управляющих сигналов.
• Перечислите этапы синтеза ОА процедурного типа канонической структуры.
• Проведите синтез ОА для выполнения умножения (используйте упрощенный
• алгоритм косвенного умножения беззнаковых чисел).
• Приведите пример умножения чисел по алгоритму косвенного умножения.
• Опишите основные варианты (схемы) косвенного умножения.
• Постройте временную диаграмму ОА для умножения. Поясните ее.
• Синтезируйте алгоритм выполнения арифметической операции по вариантам.
• Синтезируйте схему ОА по вашему алгоритму.
• Каково назначение Управляющего Автомата (УА) ?
• Роль информационных и управляющих сигналов.
• Типы УА.
• Перечислите этапы синтеза УА с жесткой логикой.
• Опишите основные триггеры как элементарные конечные автоматы.
• Каковы особенности синтеза УАЖЛ на разных типах триггеров ?
• Приведите структурные схемы автоматов Мили и Мура. В чем их отличия ?
• Опишите модели абстрактных автоматов Мили и Мура.
• Какие формы описания абстрактных конечных автоматов Вы знаете ?
• Постройте таблицы переходов / выходов и графы автоматов по схеме
• алгоритма.
• Проведите синтез УА для реализации алгоритма умножения (используйте
• упрощенный алгоритм косвенного умножения беззнаковых чисел) как
• автомат Мили / Мура.
• Постройте временную диаграмму УА для умножения. Поясните ее.
• Синтезируйте схему УАЖЛ для вашего алгоритма по вариантам.

Использование регулярных выражений (РВ). Программная реализация автоматов

• Понятие о регулярных выражениях и автоматах-распознавателях
• Краткие сведения о регулярных выражениях (РВ). Диалекты РВ.
• Применение РВ в программировании
• Пример формирования регулярного выражения
• Пример работы с регулярным выражением для контроля вводимых пользователем IP адресов.
• Синтез детерминированного автомата для распознавания языка, задаваемого регулярным выражением, и его программная реализация.
• Преобразование РВ в НКА с ε – переходами
• Преобразование НКА с ε-переходами в НКА без ε-переходов
• Получение ДКА по НКА без ε-переходов
• Минимизация ДКА
• Получение РВ по КА
• Программная реализация ДКА-распознавателя

Вопросы из первого раздела для самоконтроля:

• Что такое регулярное выражение ?
• Где используются РВ ?
• Какие Вы знаете способы задания РВ ?
• С помощью каких автоматов распознаются языки, задаваемые РВ ?
• Что такое НКА ? ДКА ?
• Как построить по РВ КА – распознаватель ?
• Как построить по РВ ДКА – распознаватель ?
• Как устранить e-переходы в КА ?
• Как минимизировать КА – распознаватель ?
• Как используются РВ в среде VS ?
• Как РВ поддерживаются в .NET Framework ?
• Опишите заданные цепочки с помощью РВ.
• Какие цепочки задает данное РВ (примеры, характеристика).
• Стратегии реализации поддержки РВ в программных системах.
• Способы использования поддержки РВ при составлении программ обработки текстов.
• Какие задачи обработки текстов решаются с помощью РВ ?
• Перечислите известные Вам программные системы, поддерживающие РВ.