Теория автоматов (шпаргалки)

Строки. Префиксы, суффиксы, подстроки. Языки.
Форма Бэкуса-Наура. Дерево вывода. Синтаксические и семантические деревья.
Замыкание Клини.
Контекстная грамматика.
Контекстно-свободная гр-ка(КС/Г).
Регулярные языки.
Порождающие грамматики. Виды, примеры.
Классификация языков по Хомскому. Примеры.
Регулярные грамматики и конечный автомат.
Автоматы и теория алгоритмов.
Распознавание мн-в автоматами.
Распознаватели, задачи, виды распознавателей.
Машина Тьюринга. Вычисление функций МТ.
Структура МТ.
Магазинный автомат (МП). Определение, структура, задание автомата.
Детерминированный МП автомат. Распознавание цепочек.
Сеть Петри. События и условия. Маркировка. Переходы. Граф достижимых маркировок СП.
Классификация сетей Петри. Применение СП в теории автоматов.
Эквивалентность автоматов.
Минимизация абстрактных автоматов (методы и примеры).
Соединения автоматов: последовательное, параллельное, с обратной связью.
Сеть автоматов.
Синтез абстрактных автоматов: исключение недоступных состояний, минимизация.
Классы булевых функций.
Сохраняющей константу ноль.
Сохраняющей константу единица.
Линейной.
Монотонной.
Двойственными.
Определение абстрактного автомата. Автоматы Мили и Мура.
Способы задания автоматов. Реакции автоматов.
Табличный способ.
Графический способ.
Асинхронный автомат.
Связь между моделями Мили и Мура.
Структурный автомат, состояния элементов памяти. Переход от абстрактного к структурному автомату.
Канонический метод структурного синтеза автоматов(модель дискретного преобразователя Глушкова).
Графический метод синтеза структурного автомата.
Табличный метод синтеза структурного автомата.
Элементарные автоматы.
Гонки в автоматах.
Аппаратные противогоночные средства.
Основные задачи кодирования состояний автомата.
Явление риска логических схем. Причины, методы борьбы.
Построение комбинационной схемы автомата: ограничения по базису, по колич-ву входов и выходов.
Минимизация сложности комбинационных схем: аналитический метод, метод Карт Карно(3,4,5 переменных).
Минимизация сложности комбинационных схем: метод Квайна-Мак-Класски.
Абсолютно минимальные формы при синтезе комбинационных схем.

7 страниц WORD (6 шрифт)

Предварительный просмотр