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

Упражнение 1:

Номер 1

Автомат Мили  может быть задан в виде

Ответ:

(1) таблиц переходов и выходов

(2) матриц

(3) графа

Номер 2

Если из любого состояния автомата достижимы все его состояния, то такой автомат называется

Ответ:

(1) сильно связным

(2) полно связным

(3) слабо связным

Номер 3

Алфавит  автомата  называется взвешенным, если

Ответ:

(1) каждому входному символу math

из алфавита math

поставлено в соответствие некоторое отрицательное число math

(2) каждому входному символу math

из алфавита math

поставлено в соответствие некоторое положительное число math

(3) каждому входному символу math

из алфавита math

поставлен в соответствие math

Упражнение 2:

Номер 1

Если состояние  не является концом ни одной дуги автомата , т.е  не достижимо ни из одного состояния, отличного от , то оно называется

Ответ:

(1) тупиковым

(2) замкнутым

(3) переходящим

Номер 2

Эксперимент, предполагающий подачу на вход автомата такой последовательности, которая определена заранее, т. е. до начала эксперимента, называется

Ответ:

(1) безусловным

(2) условным

(3) оределенным

Номер 3

Эксперимент, предполагающий подачу на вход автомата двух или более подпоследовательностей, в котором каждая последующая подпоследовательность, кроме первой, формируется на основании реакций, вызываемых предыдущими подпоследовательностями называется

Ответ:

(1) безусловным

(2) условным

(3) независимым

Упражнение 3:

Номер 1

Задача отыскания начального (стартового) состояния заданного автомата называется

Ответ:

(1) установочной

(2) диагностической

(3) аналитической>

Номер 2

Задача установки автомата в известное состояние называется

Ответ:

(1) диагностической

(2) установочной

(3) аналитической

Номер 3

Укажите верное утверждение:

Ответ:

(1) по наблюдаемой реакции на установочную последовательность автомата math

, находящегося в неизвестном для наблюдателя начальном состоянии, всегда однозначно можно определить это начальное (стартовое) состояние

(2) по наблюдаемой реакции на синхронизирующую последовательность автомата math

, находящегося в неизвестном для наблюдателя начальном состоянии, всегда однозначно можно определить это начальное (стартовое) состояние

(3) по наблюдаемой реакции на диагностическую последовательность автомата math

, находящегося в неизвестном для наблюдателя начальном состоянии, всегда однозначно можно определить это начальное (стартовое) состояние

Упражнение 4:

Номер 1

Один автомат будем называть копией другого, если

Ответ:

(1) они имеют одинаковые графы переходов

(2) они оба являются очень похожими

(3) перед началом эксперимента оба они находятся в одном и том же состоянии

Номер 2

Под -множеством автомата  понимается любая конечная совокупность состояний , не все из которых обязательно различны. Если все элементы -множества совпадают друг с другом, то оно именуется

Ответ:

(1) кратным

(2) равным

(3) однородным

Номер 3

Укажите правильное утверждение:

Ответ:

(1) располагая методами построения минимальных по весу синхронизирующих, установочных и диагностических последовательностей для автоматов со взвешенным входным алфавитом, всегда можно построить соответствующие последовательности, минимальные по длине, положив вес каждого символа алфавита math

равным единице

(2) располагая методами построения минимальных по весу синхронизирующих, установочных и диагностических последовательностей для автоматов со взвешенным входным алфавитом, всегда можно построить соответствующие последовательности, максимальные по длине, положив вес каждого символа алфавита math

равным единице

(3) располагая методами построения максимальных по весу синхронизирующих, установочных и диагностических последовательностей для автоматов со взвешенным входным алфавитом, всегда можно построить соответствующие последовательности, минимальные по длине, положив вес каждого символа алфавита math

равным единице

Упражнение 5:

Номер 1

Дерево преемников является

Ответ:

(1) бесконечной структурой

(2) конечной структурой

(3) однородной структурой

Номер 2

Укажите верное утверждение:

Ответ:

(1) в общем случае установочная последовательность является одновременно максимальной по весу и по длине

(2) в общем случае установочная последовательность может не быть одновременно минимальной по весу и по длине

(3) в общем случае установочная последовательность является одновременно минимальной по весу и по длине

Номер 3

Укажите верное утверждение:

Ответ:

(1) в общем случае синхронизирующая последовательность автомата может быть минимальной по весу, но не являться минимальной по длине

(2) в общем случае синхронизирующая последовательность автомата должна быть минимальной по весу и по длине

(3) в общем случае синхронизирующая последовательность автомата должна быть максимальной по весу и по длине

Упражнение 6:

Номер 1

При построении синхронизирующего дерева автомата  с множеством  допустимых начальных состояний вершина  -го уровня становится листом, если

Ответ:

(1)

(2) она является однородной

(3) на уровнях, предшествующих math

-му, имеется такая вершина math

, что

, но значение флажка вершины math

больше значения флажка вершины math

(4) на уровнях, предшествующих math

-му, имеется такая вершина math

, что

, а значение флажка вершины math

больше значения флажка вершины math

Номер 2

При построении установочного дерева автомата автомата  с множеством  допустимых начальных состояний вершина  -го уровня становится листом, если

Ответ:

(1) она является однородной

(2) она является простой>

(3) она является кратной

(4) на уровнях, предшествующих math

-му, имеется такая вершина math

, что

, но значение флажка вершины math

больше значения флажка вершины math

(5) на уровнях, предшествующих math

-му, имеется однородная или простая вершина math

, значение флажка которой меньше значения флажка вершины math

Номер 3

При построении диагностического дерева автомата автомата  с множеством  допустимых начальных состояний вершина  -го уровня становится листом, если

Ответ:

(1) она является простой

(2) она является однородной

(3) она является кратной

(4) на уровнях, предшествующих math

-му, имеется такая вершина math

, что

, но значение флажка вершины math

больше значения флажка вершины math

(5) на уровнях, предшествующих math

-му, имеется простая вершина math

, значение флажка которой меньше значения флажка вершины math

Упражнение 7:

Номер 1

Построение графа синхронизации автомата осуществляется

Ответ:

(1) рекурсивно

(2) последовательно

(3) индуктивно

Номер 2

Построение графа установки автомата осуществляется

Ответ:

(1) рекурсивно и по существу совпадает с процессом построения установочного дерева

(2) рекурсивно и никогда не совпадает с процессом построения установочного дерева

(3) последовательно

Номер 3

Укажите правильное утверждение:

Ответ:

(1) задача синтеза синхронизирующей последовательности может быть сведена к задаче выбора наискорейшего пути, решаемой только методом прямого перебора

(2) задача синтеза синхронизирующей последовательности может быть сведена к задаче выбора наискорейшего пути, решаемой методом динамического программирования

(3) задача синтеза синхронизирующей последовательности может быть сведена к задаче выбора наискорейшего пути, решаемой только аналитическими методами

Упражнение 8:

Номер 1

Укажите правильное утверждение:

Ответ:

(1) для решения задачи синтеза максимальной по весу синхронизирующей последовательности, необходимо построить таблицу переходов-выходов графа синхронизации автомата, и найти в нем минимальной по весу СП методом динамического программирования

(2) для решения задачи синтеза минимальной по весу синхронизирующей последовательности, необходимо построить таблицу переходов-выходов графа установки автомата, и найти в нем минимальной по весу СП методом динамического программирования

(3) для решения задачи синтеза минимальной по весу синхронизирующей последовательности, необходимо построить таблицу переходов-выходов графа синхронизации автомата, и найти в нем минимальной по весу СП методом динамического программирования

Номер 2

Укажите правильное утверждение:

Ответ:

(1) для решения задачи синтеза минимальной по весу установочной последовательности, необходимо построить таблицу переходов-выходов графа установки автомата, и найти на нем минимальную установочную последовательность

(2) для решения задачи синтеза минимальной по весу установочной последовательности, необходимо построить таблицу переходов-выходов графа синхронизации автомата, и найти в нем минимальной по весу СП методом динамического программирования

(3) для решения задачи синтеза максимальной по весу установочной последовательности, необходимо построить таблицу переходов-выходов графа установки автомата, и найти на нем минимальную установочную последовательность

Номер 3

Укажите правильное утверждение:

Ответ:

(1) для решения задачи синтеза минимальной по весу диагностической последовательности, необходимо построить таблицу переходов-выходов графа диагностики автомата, и найти на нем минимальную диагностическую последовательность

(2) для решения задачи синтеза минимальной по весу диагностической последовательности, необходимо построить таблицу переходов-выходов графа диагностики автомата, и найти на нем минимальную диагностическую последовательность

(3) для решения задачи синтеза минимальной по весу диагностической последовательности, необходимо построить таблицу переходов-выходов графа диагностики автомата, и найти на нем минимальную диагностическую последовательность

Теория экспериментов с конечными автоматами - тест 2