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

Если

- компенсирующая система минимальной длины для (a,b)

-обхода графа G(S,U)

, то

Вершину

графа

, у которой $\Delta (s)>0$ называется

Для правильного графа G(S,U)

обход длины |U|

существует тогда и только тогда, когда

Если для ЛА $\tilde A$ в любой момент времени

выход

зависит лишь от предыдущих $\mu$ входов,то ЛА $\tilde A$ является

Если для заданного ЛА

существует такое натуральное число N(A)

, что знания начального отрезка длины N(A)

слова w достаточно для однозначного определения первого символа слова

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

и начального состояния ЛА, то

называют ЛА

Пусть для каждой вершины

разветвления удалось получить оценку снизу для лучшего решения из множества

: $f(U')\le min_{\hat u \in U'}W(\hat u)$ . Функция

является

В приведенном рисунке для наблюдения реакции выделен 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-му входному каналу неизвестного входного слова является

В приведенном рисунке для наблюдения реакции выделен 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-му входному каналу неизвестного входного слова является

В приведенном рисунке для наблюдения реакции выделен 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-му входному каналу неизвестного входного слова является

Если характеристические матрицы

и $F_i, i=\overline{1,l}$ , БС $\tilde A$ являются верхними (нижними) треугольными, где

- число строк и столбцов упомянутых матриц, то для этой БС существуют СП длины

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

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