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

Количество вопросов - 192

Состояние, в котором рассматриваемый ЛА оказывается после подачи ОСП, называется

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

Для автоматов с большим числом состояний построить граф переходов

Пусть для каждой вершины U' разветвления удалось получить оценку снизу для лучшего решения из множества U': f(U')\le min_{\hat u \in U'}W(\hat u). Функция fявляется

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

L-матрица неоднородной системы уравнений \sum_{i=1}^lF_iu_i=-A. Если rankL < l, то

Существующие методы контроля ЦУ подразделяются на

Если для ЛА \tilde A в любой момент времени t выход y(t) зависит лишь от предыдущих \mu входов,то ЛА \tilde A является

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

Если характеристические матрицы A и F_i, i=\overline{1,l}, БС \tilde A являются верхними (нижними) треугольными, где n- число строк и столбцов упомянутых матриц, то для этой БС существуют СП длины

Для сильно связного графа G(S,U), |S|=n степени m и диаметра d имеет место неравенство

Для того чтобы БА \tilde A был БА БПИ-\bar s(0), необходимо и достаточно, чтобы для любого состояния \bar s \in R(\bar s(0)) выполнялось условие

Состоянием равновесия любого свободного ЛА является

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

Состояние равновесия ДЛС устойчиво в большом, если

Длиной d(p^G_{min}) графа G(S,U) является

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

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

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

Каково количество перепадов в послежовательности 01110110

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

Если (\tilde A)=S_n, то необходимым и достаточным условием существования СП длины t+1 для НЛА является

Запись вида b=[\underline b, \bar b], где \underline b > \bar b, интерпретируется как множество GF(p) [\bar b +1, \underline b -1 > и называется

Задача преобразования произвольного автомата в ОБПИК-автомат порядка 1 осуществляется путем

БА \tilde A является БА CБПИ, если

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

Для того чтобы у ЛА A существовал подавтомат ОБПИ A(I,J), где I и J - непустые собственные подмножества множеств входных и выходных каналов ЛА соответственно, необходимо и достаточно, чтобы

Если для \mu-ЛА существует хотя бы одна ОСП длины k, то обобщенными СП для него являются любые входные последовательности длины

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

Пусть \hat {u_{min}} - минимальная ОСП, а u - произвольная ОСП длины k \ge k_{min}, переводящая ЛА в одно и то же синхросостояние, и пусть W(\bar u) \ge 0 для любого входного символа этого ЛА. Тогда

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

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

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

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

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

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

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

ОБПИ-автоматы в качестве частного случая включают в себя

Если выполняется \sigma(s, \bar p)=\sigma(t, \bar q)pr_{1,...,\mu}\lambda(s, \bar p)=pr_{1,...,\mu}\lambda(t, \bar q) \to pr_{1,...,\nu}\bar p \ne pr_{1,...,\nu}\bar q, то пара состояний s и t называется

Если из ориентированного конечного графа G(A) удалить все вершины вида \{s,s\} вместе с инцидентными им дугами, если последние, в свою очередь, инцидентны только вершинам такого же вида, а также изолированные вершины, то полученный в результате такого удаления ориентированный конечный граф называется

Если в проверочном графе ОБПИК-автомата A длина максимального пути, начальная дуга которого является выделенной, равна t, то порядок ОБПИК-автомата N(A) равен

Пусть автомат A не является ОБПИК-автоматом,S_0 =\{1,2,3\}, t=1, тогда N(A)

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

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. S_0 =\{1,2\}. На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1.\hat S =\{1,2,3\}, L=01,01.Если состояние автомата равно 3, то конечное состояние будет равно

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. S_0 =\{1,2\} На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1.\hat S =\{1,2,3\}, L=01,01.Если \hat s_k_i =3, то проекцией по 1-му входному каналу неизвестного входного слова является

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

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

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

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

Если м - компенсирующая система минимальной длины для (a,b)-обхода графа G(S,U), то

Длина кратчайшего простого безусловного эксперимента, позволяющего распознавать функцию выходов сильно связного неинициального автомата A=(S,X,Y,\delta,\lambda), где |S|=n,|X|=m , не превышает величины

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

Один из принципов построения схемы встроенного контроля (СВК) для комбинационных устройств (КУ), используемый на практике, базируется на

Принцип построения СВК может быть использован и для

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

Структурная схема ЛА состоит из соединения конечного числа элементарных составляющих, каждая из которых мгновенно выполняет:

Если усилитель равен -1, то он

Если \forall s_{j_1},s_{j_2} \in S\delta (s_{j_1},p)=\delta (s_{j_2},p), то входная последовательность p=x_{i_1},x_{i_2},...,x_{i_n} является

Для того чтобы ЛА А имел СП длины k, необходимо и достаточно, чтобы

Обобщенной диаграммой переходов для \mu-ЛА над полем GF(p) называется ориентированный граф, содержащий

Если для \mu-ЛА существует хотя бы одна обобщенная ДП длины k, то для него обобщенными являются любые входные последовательности длины

Если поведение ДС описывается уравнением \bar s (t+1)=A \bar s(t)+B \bar u(t)+B_1 \bar u(t-h), то она

Состояние равновесия \bar s свободного ЛА \tilde A при \forall \bar s \in S_n \exists k \in Nt>k \to \bar s(t)=\bar s называется

Линейный автомат называется автоматом БПИ, если

Для того чтобы ЛА A являлся ЛА БПИ, необходимо и достаточно, чтобы рангхарактеристической матрицы D равнялся

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

Если исходный ЛА не является автоматом БПИ, то оптимальный ОБПИ подавтомат, если таковой существует, можно найти методом перебора начиная с подавтомата A(H,H), где

Пусть задано некоторое конечное множество ЛА \tilde A={A_1,...,A_k}, которое называется базисом, а каждый элемент этого множества - базисным. Предполагается, что сеть содержит в качестве компонентов ЛА A_i \in \tilde A. Помимо элементов сеть содержит входные и выходные полюсы. Из базисных элементов сети будут строиться по определенным правилам:

Для того чтобы ЛА был неизбыточным по выходам, необходимо и достаточно, чтобы

Множество путей в сети, связывающее каждый внешний вход сети с одним из ее внешних выходов, называется

Мощность множества всех различных синхросостояний ЛА, заданного над полем GF(p), равна

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

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

Каково количество перепадов в послежовательности 00101011

Два интервала a=[\underline a, \bar a] и b=[\underline b, \bar b] называются равными, если

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

Мощность множества всех решений интервальной системы уравнений с квадратной матрицей равна величине z=\prod_{i=1}^n \omega (B_i). При увеличении ширины интервалов, мощность

Для того чтобы входная последовательность u(0),\bar u(1),...,\bar u(t) была СП для БC \tilde A, достаточно, чтобы по крайней мере для одного из значений i=0,1,...,t выполнялось

Выберете правильное утверждение:

Для автоматов, заданных графом переходов, задача синхронизации и установки автоматов сводится к задаче

Для того чтобы последовательность u(0),\bar u(1),...,\bar u(t) была ДП для БА \tilde A размерности n, необходимо и достаточно, чтобы

Cостояние \bar s_j БА достижимо из состояния \bar s_j, если

БА \tilde A является БА БПИ, если

Если уравнение состояния БА имеет вид
\bar s(t+1)=A \bar s(t)+ \left(\sum_{i=1}^lF_i^{(0)}u_i(t)\right)\bar s(t)+\left(\sum_{i=1}^h u_i(t-h)\right)\bar s(t)+B_0 \bar u(t)+B_h u(t-h)
то БА

Билинейные автоматы с запаздыванием являются частным случаем общих билинейных систем с распределенным запаздыванием, где соответствующие матрицы (запаздывание на 1, 2, ..., h-1 такт) являются

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

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

Вид контроля, который ведется непрерывно в процессе функционирования устройства и параллельно с его работой называется

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

Если для любого t свободного ЛА \tilde A \bar s=\bar s(t) то состояние \bar s называется состоянием равновесия, если для любого

ЛА называется неизбыточным по выходам, если

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

Восстановление неизвестной входной последовательности по известному начальному состоянию автомата и наблюдаемой реакции в случае ЛА сводится к

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

Если A(I,J) является оптимальным ОБПИ подавтоматом ЛА A, то

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

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

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

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

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

Выходной канал y_i ЛА назовем избыточным, если

Для того чтобы ЛА был БПИ и неизбыточным по выходам, необходимо и достаточно, чтобы

БА \tilde A называется БА без потери информации из состояния \bar s (БПИ-\bar s, если

Вершину s графа G(S,U), у которой \Delta (s)>0 называется

Решение проблемы повышения надежности цифровых устройств (ЦУ)

Для того чтобы входная последовательность u(0),\bar u(1),...,\bar u(t) была СП для БА \tilde A, необходимо и достаточно, чтобы выполнялось

Тест - это

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

Если в ОДП для любой пары вершин \bar a и \bar b существует путь, ведущий из \bar a в \bar b, то такая ОДП называется

Сеть, в которой отсутствуют незадействованные входы используемых в ее составе базисных элементов, называется

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

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

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

При построении установочного дерева автомата автомата A с множеством S_{0} допустимых начальных состояний вершина S k-го уровня становится листом, если

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

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

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

Для того, чтобы однозначно определить число N(A) оно должно быть

Для решения задачи контроля сети автоматов, исходный произвольный автомат следует преобразовывать в БПИ-автомат

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. S_0 =\{1,2\} На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1.\hat S =\{1,2,3\}, L=01,01.Если \hat s_k_i =2, то проекцией по 1-му входному каналу неизвестного входного слова является

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

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

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

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

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

Задержка имеет

Если \forall s_{j_1},s_{j_2} \in S\lambda (s_{j_1},p)=\lambda (s_{j_2},p) \to s_{j_1}=s_{j_2}, то входная последовательность p=x_{i_1},x_{i_2},...,x_{i_n} является

Если для ЛА А существует хотя бы одна СП длины k, то для этого автомата синхронизирующими являются любые входные последовательности, длина которых

Если для НЛА \tilde A существует хотя бы одна УП длины t, то длина его входной установочной последовательности может быть равна

Для того чтобы \mu-ЛА A размерности n имел обобщенную ДП длины t, необходимо и достаточно, чтобы

Если ДС запаздывает по состоянию, то ее поведение описывается уравнением:

Для того чтобы ЛА был автоматом СБПИК-k, необходимо и достаточно, чтобы \bar G_1(k) была

Заметим, что если у ЛА, для которого ищется оптимальный подавтомат, ОБПИ таков, что m>l, то этот подавтомат является

Линейное уравнение a+X=b, где a,b - обычные интервалы над полем FG(p), имеет алгебраическое решение X в виде обобщенного интервала тогда и только тогда, когда

Каково количество перепадов в послежовательности 011000111010

Интервал вида a=[\underline a, \bar a], где \underline a = \bar a интерпретируется как элемент поля GF(p)называется

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

L-матрица неоднородной системы уравнений \sum_{i=1}^lF_iu_i=-A. Если rankL=l, то

Если последовательность u(0),\bar u(1),...,\bar u(t) является для БА диагностической, то это означает, что

Для того чтобы БА \tilde A был БА БПИ, необходимо и достаточно, чтобы для любого состояния \bar s \in S_n L(\bar s) был равен

Если уравнение состояния БА имеет вид
\bar s(t+1)=A_0 \bar s(t)+A_h \bar s(t-h)+ \left(\sum_{i=1}^lF_i^{(0)}u_i(t)\right)\bar s(t)+\left(\sum_{i=1}^lF_i^{(h)}u_i(t)\right)\bar s(t-h)+B \bar u(t)
то БА

Для билинейных автоматов с распределенным запаздыванием по управлению для однозначности определения состояний для t > 0необходимо

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

Если \forall s_{j_1},s_{j_2} \in S\lambda (s_{j_1},p)=\lambda (s_{j_2},p) \to \delta (s_{j_1},p)=\delta (s_{j_2},p), то входная последовательность p=x_{i_1},x_{i_2},...,x_{i_n} является

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

Если усилитель равен 0, то он

Если ДС запаздывает по управлению, то ее поведение описывается уравнением:

Автомат называется оптимальным, если

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. S_0 =\{1,2\} На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1.\hat S =\{1,2,3\}, L=01,01.Если \hat s_k_i =1, то проекцией по 1-му входному каналу неизвестного входного слова является

ЛА \tilde A, заданный над полем GF(p) уравнением \bar s (t+1)=A \bar s(t)+B \bar u(t) при \bar u(t)=[0] для любого t называется

Если для ЛА \tilde A, у которого характеристическая матрица C невырожденная, существует хотя бы одна УП длины k+1, то длина его входной установочной последовательности может быть равна

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

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. S_0 =\{1,2\}. На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1.\hat S =\{1,2,3\}, L=01,01.Если состояние автомата равно 1, то конечное состояние будет равно

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

Если для ЛА \tilde A в любой момент времени t выход y(t) однозначно определяется входом в этот же момент и предыдущими \mu входами и \mu выходами,то ЛА

При использовании СВК при k;0, сигнал на выходе возникшей неисправности в ЦУ появится

Возвращение системы в определенное состояние фазового пространства всякий раз, когда она из него выводится называется

ОБПИК-автоматы в качестве частного случая включают в себя

Сумматор имеет

Обобщенными автоматами без потери информации (ОБПИ-автоматами) называются

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

Продолжите утверждение. Каждой комбинации из N(A) символов, являющихся проекциями реакций автомата A по выходным каналам с номерами 1,...,\mu, однозначно соответствует искомая проекция

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

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

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

Если главная характеристическая матрица ЛА размерности n является верхней треугольной, то длина минимальной СП для этого ЛА может быть

Каждому обобщенному состоянию (ОС) линейного автомата соответствует

Если у \mu-ЛА размерности n ранг характеристической матрицы C равен n, то для него существует обобщенная УП, длина которой равна

Для того чтобы свободный ЛА над полем GF(p) имел асимптотически устойчивое состояние равновесия, необходимо и достаточно, чтобы существовало такое натуральное k, для которого

Автоматы, являющиеся неинициальными, т. е. такими, у которых начальное состояние неизвестно, называются

Если для заданного ЛА A существует такое натуральное число N(A), что знания начального отрезка длины N(A) слова w достаточно для однозначного определения первого символа слова p независимо от входной последовательности p и начального состояния ЛА, то A называют ЛА

Линейный автомат называется неизбыточным по выходам, если

Подмножество \subseteq GF(p), такое, что a=[\underline a, \bar a]={\alpha \underline a \le \alpha \le \bar a; \underline a, \bar a \in GF(p)}называестя

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

Если свободный ЛА над полем GF(p) имеет асимптотически устойчивое состояние, то оно

Если для \mu-ЛА размерности n существуют обобщенные ДП, то длина таких минимальных последовательностей

Если уравнение выхода БА имеет вид
\bar y(t)=C \bar s(t)+ \left(\sum_{i=1}^lG_i^{(0)}u_i(t)\right)\bar s(t)+\left(\sum_{i=1}^h G_i^{(h)}u_i(t-h)\right)\bar s(t)+D_0 \bar u(t)+D_h \bar u(t-h)
то БА

Если для \mu-ЛА размерности n существует хотя бы одна обобщенная УП длины k, то для этого автомата обобщенными УП являются любые входные последовательности длины

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

Задачи синхронизации и установки автоматов - это разновидности задачи управления дискретной системой (ДС), которая в общем виде формулируется следующим образом:

Для того чтобы входная последовательность u(0),\bar u(1),...,\bar u(t) была УП для БА \tilde A, необходимо и достаточно, чтобы для каждого ненулевого состояния \bar s \in S_nвыполнялось:

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. S_0 =\{1,2\}. На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1.\hat S =\{1,2,3\}, L=01,01.Если состояние автомата равно 2, то конечное состояние будет равно

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

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

Если усилитель равен 1, то он

Если у неизбыточных по выходам ЛА A оптимальный подавтомат ОБПИ существует, то он

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

При построении диагностического дерева автомата автомата A с множеством S_{0} допустимых начальных состояний вершина S k-го уровня становится листом, если

Выберете правильное утверждение

Для билинейных автоматов с распределенным запаздыванием по состоянию для однозначности определения состояний для t > 0необходимо задать состояния в моменты времени

Для того чтобы ЛА над полем GF(p) имел асимптотически устойчивое состояние, необходимо и достаточно, чтобы он был

Если ЛА является обобщенно синхронизируемым, то для любого k \ge k_{min} множество синхросостояний, порождаемых всеми ОСП длины k, совпадает с множеством синхросостояний, порождаемых всеми ОСП длины