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

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

Номер 1

 Рисунок иллюстрирует ДУ с памятью, описываемое математической моделью конечного автомата Мили. На данном рисунке блок В

Ответ:

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

(2) является комбинационным устройством

(3) реализует функцию выходов

Номер 2

 Рисунок иллюстрирует ДУ с памятью, описываемое математической моделью конечного автомата Мили. На данном рисунке блок С

Ответ:

(1) реализует функцию выходов

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

(3) является комбинационным устройством

Номер 3

Рисунок иллюстрирует ДУ с памятью, описываемое математической моделью конечного автомата Мили. Выберете верные утверждения: На данном рисунке блок С

Ответ:

(1) С реализует функцию выходов

(2) В представляет собой запоминающее устройство

(3) С реализует функцию входов

(4) В представляет собой запоминающее устройство и является комбинационным устройством

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

Номер 1

Функция выходов будет распознана, если

Ответ:

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

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

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

Номер 2

Проведение простого безусловного эксперимента должно включать:

Ответ:

(1) построение соответствующего входного слова

(2) наблюдение реакции автомата на входное слово

(3) сравнение на основе полученной реакции функции выходов исследуемого автомата с эталоном

(4) вывод заключения об исправности

Номер 3

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

Ответ:

(1) исследуемым автоматом math

(2) контролирующий автоматом math

(3) исследуемым автоматом math

и контролирующий автоматом math

одновременно

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

Номер 1

Если автомат задан в виде ориентированного графа, у которого начальной является вершина , то входному слову в графе автомата будет соответствовать

Ответ:

(1) путь, начинающийся в math

и проходящий через половину его дуг

(2) путь, начинающийся в math

и проходящий через все его дуги

(3) путь, заканчивающийся в math

и проходящий при этом через все его дуги

Номер 2

Обходом графа называется

Ответ:

(1) путь, приходящий в начальную вершину math

и проходящий через все его дуги

(2) путь, начинающийся в начальной вершине math

и проходящий через все его дуги

(3) путь, начинающийся в начальной вершине math

и проходящий через половину его дуг

Номер 3

Путем графа называется

Ответ:

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

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

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

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

Номер 1

Пусть в распоряжении экспериментатора находится один экземпляр автомата Мили, у которого известны входной алфавит, выходной алфавит, множество состояний и функция переходов. Решение задачи построения простого безусловного эксперимента позволяет

Ответ:

(1) распознать функцию выходов автомата или эквивалентного ему автомата

(2) решать задачу контроля функции выходов инициального автомата

(3) решать и задачу контроля функции входов инициального автомата

Номер 2

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

Ответ:

(1) задаче построения обхода полуавтоматного графа

(2) задаче построения перехода автоматного графа

(3) задаче построения обхода автоматного графа

Номер 3

Для того чтобы у графа  существовал обход, необходимо и достаточно, чтобы

Ответ:

(1) для любой вершины math

существует путь, связывающий вершину math

с вершиной math

(2) в любом слое math

графа существует не более одной вершины math

(3) в графе math

существует не более одной дуги math

, таких, что math

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

Номер 1

Выберете верное утверждение

Ответ:

(1) характеристическое слово автомата в точности соответствует пути по графу этого автомата

(2) характеристическое слово автомата не соответствует пути по графу этого автомата

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

Номер 2

Длиной  графа  является

Ответ:

(1) кратчайший обход графа

(2) число дуг, входящих в обход

(3) число дуг, выходящих из обхода

Номер 3

Для правильного графа  обход длины  существует тогда и только тогда, когда

Ответ:

(1) в каждой вершине графа число исходящих дуг равно числу заходящих

(2) в начальной вершине math

графа число исходящих дуг на единицу больше числа заходящих, и существует такая вершина math

, в которой число исходящих дуг на единицу меньше числа заходящих

(3) каждой вершине графа число исходящих дуг не равно числу заходящих

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

Номер 1

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

Ответ:

(1) эйлеровым путем

(2) эйлеровым контуром

(3) исходящим путем

Номер 2

Вершину  графа , у которой  называется

Ответ:

(1) положительной

(2) отрицательной

(3) мнимой

Номер 3

Если  - компенсирующая система минимальной длины для -обхода графа , то

Ответ:

(1)

(2)

(3)

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

Номер 1

        Для сильно связного графа  степени  и диаметра  имеет место неравенство

Ответ:

(1)

(2)

(3)

Номер 2

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

Ответ:

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

(2) не связан

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

Номер 3

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

Ответ:

(1)

(2)

(3)

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

Номер 1

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

Ответ:

(1) множество math

путей в графе math

, исходящих из начальной вершины math

этого графа, называется покрытием, если каждая дуга math

принадлежит некоторому пути из math

(2) множество math

путей в графе math

, исходящих из любой вершины math

этого графа, называется покрытием, если каждая дуга math

принадлежит некоторому пути из math

(3) множество math

путей в графе math

, исходящих из начальной вершины math

этого графа, называется покрытием, если каждая дуга math

принадлежит некоторому пути из math

Номер 2

Укажите верные выражения

Ответ:

(1) число путей покрытия называется его кратностью

(2) сумма длин всех путей покрытия называется его длиной

(3) число путей покрытия называется его длиной

(4) сумма длин всех путей покрытия называется его кратностью

Номер 3

Пусть  - множество всех тех вершин графа , из которых исходит хотя бы одна дуга. Тогда

Ответ:

(1) покрытие графа math

существует тогда и только тогда, когда любая вершина множества math

достижима из начальной

(2) покрытие графа math

существует тогда и только тогда, когда любая вершина множества math

не достижима из начальной

(3) покрытие графа math

существует тогда и только тогда, когда только начальная вершина множества math

достижима из начальной

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