Теория автоматов вопросы к экзамену



Теория автоматов вопросы к экзамену

Определение конечного автомата.

Классификация конечных автоматов.

Способы задания конечных автоматов.

Неотличимость состояний, построение графа условий неотличимости.

Алгоритм Мура.

Минимизация полных автоматов по разбиению на классы неотличимости.

Совместимость состояний, построение графа условий совместимости.

Сохраняемое правильное покрытие и минимизация частичного автомата.

Метод последовательных сокращений.

Классификация элементов и логических сетей.

Анализ комбинационной схемы.

Синтез комбинационной схемы.

Анализ последовательностной схемы.

Синтез последовательностной схемы. Функции возбуждения триггеров.

Проблема опасных состязаний.

Принципы построения полного проверяющего теста

Методы генерации тестов

Структурные методы построения тестов. Метод критических путей

Структурные методы построения тестов. Метод различающей функции

Структурные методы построения тестов. Метод активизации одномерного пути

Схема построения легкотестируемого устройства

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

Построение тестов для константных неисправностей

Минимизация полного теста

Тестирование последовательностных схем

Общие сведения о самопроверяемых цифровых устройствах

Построение обобщенного графа



Построение общей таблицы истинности

Синтез самопроверяемых СВК

Синтез самопроверяемых комбинационных схем

Разделимые и неразделимые коды



Основные понятия. Способы задания языков.

Два вида грамматик. Конечный автомат-распознаватель. Способы задания автоматов.

Распознаваемое слово. Распознаваемый автомат. Лемма о накачке.

Детерминизация автоматов. Теорема об эквивалентности детерминированных и недетерминированных автоматов.

Регулярные языки. Регулярные выражения. Граф-переходов.

Теорема Клини. Доказательство теоремы Клини. Редукция ребра, вершины.



Свойства регулярных выражений. Утверждения о регулярных языках. Операции регулирования. Теорема замкнутости.

Грамматика. Непосредственный вывод. Язык, порождаемый грамматикой. Способы задания языков. Правый и левый вывод. Приводимость.

Классификация языков по Хомскому. Алгоритм построения автомата по регулярной грамматике. Задача синтаксического анализа.

Магазинные автоматы. Распознавание языка.

Алгоритм построения МА по КС-грамматике.








sitemap
sitemap