Решенные билеты (1085496), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Вопрос 33.

Критерий нераспространения искажений автоматом, следствие для инъективного автомата.

Рассмотрим систему связи:

- искаженная последовательность ; А- левый обратный к автомату А. Если в КС были искажены k знаков, то в случае, когда в последовательности число искажений >k => произошло распространение искажений, иначе- искажения не распространились. ] : X^*Y^*, сохраняя длины, т.е. (X^l)Y^l, l; ( , )- количество номеров несовпадающих членов в этих последовательностях, т.е. ( , )= {i= x_i x_i },  , X^l (( , ) - метрика Хемпинга).

Определение: Отображение , сохраняющее длины слов- распространяющее искажения не более чем в k раз, если lN; , X^l выполняется неравенство: (( ),( ))k*( , ). Если k=1 => - отображение, нераспространяющее искажений.

Далее рассмотрим: Шифр колонной замены(буквы текста заменяются колонками) - порожденный множ-вом подстановок {g_l,tl,tN_, tl}, g_l,tG(X)S_x- (симметрическая группа подстановок), называется отображение : X^*X^*, определяемое по формуле: (x₁,…,x_l)= g_l,1(x₁),…,g_l,l(x₁); ((( )( ))=( , )), т.е. для последовательности длинны l, i-ый член последовательности заменяется на её образ по подстановке g_l,i(x_i). Если нет зависимости от l и t, то шифр колонной замены называется шифром простой замены. Шифр перестановки - порожденный множ-вом подстановок {p_llN}, p_lS_l, преобразование : X^*X^*, определяется равенством: (x₁,…,x_l)= ,…, ; (( ),( ))=( , );{=> - тоже не распространяет искажений}.

Определение. Обозначим через H(x) - множество всех биективных преобразований X*, -сохраняет длины слов и не распространяет искажений, биекция; , H(x) ={:X*->X*| - биекция, сохраняет длины слов, не распространяет искажений.

Теорема ‘теорема Маркова’: Следующие утверждения равносильны для : X^*X^*: а) - биективное отображение, сохраняющее длины слов и нераспространяющее искажения; б) =, где - некоторый шифр колонной замены, а - некоторый шифр перестановки.(без доказательства).

Пусть - произвольное рефлексивное бинарное отношение на множ-ве X: X², xx  x может исказиться в x.

Определение : А- не распространяющее искажений по , если для sS, lN, =(x₁,…,x_l), =(x₁,…,x_l)X^l: x_ix_i, i выполняется неравенство: (A_s( ),A_s( ))( , ). При =x² (т.е. разрешены любые искажения) автомат А- нераспространяющий искажений.

Теорема: Пусть A(X,S,Y,h,f) - произвольный автомат,  - произвольное рефлексивное бинарное отношение на множестве X и пусть f(s,x)f(s,x), sS; x, xX: xx, xx тогда следующие свойства равносильны: а) А- не распространяет искажений по  (внутренняя автономность по ); б) h(s,x)~h(s,x), sS, xx.

Доказательство: (а) => (б): предположим, что б)- невыполнено, тогда  =x₂,..,x_lX^l-1: A_h(s,x)(x₂,…,x_l)A_h(s,x)(x₂,…,x_l); [(x₁,x₂…,x_l),( x₁,x₂…,x_l)]=1, [A_s(x₁,x₂…,x_l),A_s(x₁,x₂…,x_l)]2 (во входных одно искажение, а в выходных 2 => получаем противоречие.); (б) => (а): Пусть s₁S, =x₁,…,x_lX^l, = x₁,…,x_lX^l, x_ix_i,i, и пусть h^*(s₁, )=s₁,…,s_l+1, h^*(s₁, )=s₁s₂,…,s_l+1 по условию б) => s_i~s_i, i2 => ( )=f(s₁,x₁),f(s₂,x₂),…,f(s_l,x_l) => ( ( ), ( ))=( , ).

Следствие:(случай =x²). Пусть A- инъективный автомат => А- не распространяет искажений  A/~- внутренне автономный т.е. этот автомат реализует только шифр колонной замены.

Вопрос 34.

Автоматы самовосстановления. Теорема о сведении автомата самовосстановления к проходной линии задержки, её единственность. Автоматы внутреннего самовосстановления.

Самовосстановление в автоматах - процесс перехода этого автомата из произвольных 2-х или более состояний в эквивалентные (т.е. в один и тот же класс эквивалентности) под действием одной и той же входной последовательности, т.е. h(s_i, )~h(s_j, ), i,j. Чем больше вероятность этого события- тем устойчивее автомат к случайным сбоям во входной последовательности, и в функции перехода, кроме того если эта вероятность слишком велика, то при необходимости обеспечить к экземпляров автомата, можно не устанавливать их в одно и тоже начальное состояние т.е. можно обойтись без принудительной синхронизации. Пусть kN, lN₀ и =(s₁,…,s_k)S^k обозначим: P_l( )=X^-1{ X^lh(s_i, )~h(s_j, )}, i,j; =S^-k - вероятность k- самовосстановления на l-ом шаге автомата А- вероятность того, что k состояний при подаче последовательности длины l перейдут в эквивалентные (равномерное распределение). Очевидно, что  , причем если = => =1, k; т.к. P_l( )P_l+1( ), l,s =>  =>  =P^(k)(A)- вероятность k-самовосстановления А.

Определение: матрица переходных состояний k-грамм- матрица вида B_k=(P( ), которая определяется как: - матрица размера S^kS^k; -строки и столбцы занумерованы векторами состояний длины k: ^k={ }; - на пересечении строки =(s₁,…,s_k) и столбца =(s₁,…,s_k) стоит вероятность: P( )=X^-1{xXh(s_i,x)=s_i)} i,k т.е. элементы матрицы- вероятность того, что перейдет в  за один такт. ] -вектор, тогда =B_k =  ,l; P₀( )= 0, если i,j: s_is_j и =1, если i,j s_i~s_j, тогда, если - нормированная сумма всех координат этого вектора, то: = => = , = , ll₀. Из последнего следует, что выполняется одно из следующих свойств: а) < <…< = =P^(k)(A) или б) < <P^(k)(A), l , т.е. либо последовательность стабилизируется, либо нет.

Определение: (A) = или l₀, тогда a), или , тогда б); -- задержка самовосстановления в А. Легко показать, что (A)= (A), k2. Пример автомата с длиной задержки самовосстановления: Автомат Мура: X=Y={0,1}. (A)=

Определение: А- самовосстановления с задержкой n, если h(s, )~h(s, ) s,sS, Xⁿ, причем, n- минимальное. Здесь n- задержка самовосстановления автомата А.

Утверждение: Для А; n,kN₀, k2 следующие свойства равносильны: а) А-самовосстановления с задержкой n; б) < =1 ( =0); в) вероятность (A)=1, (A)=n; г)  =1; (A)=n; д) память входа автомата равна n;

Доказательство: очевидно из определений.

Утверждение: Для  автомата-самовосстановления А выполняются следующие свойства: а) - связный автомат; б) Задержка эквиваалентности, задержка самовосстановления и память входа всегда совпадают. Пример: ‘Aвтомат самовосстановления’: R₀()(X,Y,S=Xⁿ)- проходная линия задержки (ПЛЗ), е сли t- минимальный номер существенной задержки , т.е. =(x_t,x_t+1,…,x_n), то задержка самовосстановления =(n-t+1).

Определение: Два автомата: A и A с одним и тем же входным алфавитом- эквивалентные с задержкой n: A A, если для s автомата А s автомата А: s s и наоборот.

Теорема:(описание автоматов самовосстановления): Пусть A=(X, S, Y, h, f)- автомат самовосстановления с задержкой не более n. Определим функции: _A,n: Xⁿ⁺¹Y; _A,n: Xⁿ равенствами: _A,n(x₁,…,x_n+1)=f(h(s,( x₁,…,x_n)),x_n+1); _A,n(x₁,…,x_n)=[h(s,( x₁,…,x_n))]_~, для  x₁,…,x_n и s, тогда: а) _А,n- функция памяти А; б) А R₀(_A,n)- т.е. для автомата-самовосстановления можно найти эквивалентную ПЛЗ; в) _A,n: R₀(_A,n) - внутренний гомоморфизм, образ которого совпадает с ( )^[c]- существенным подавтоматом А.

Доказательство: Прежде всего заметим, что определения отображения _А,n, _A,n- корректны, т.к. не зависят от s в силу определения, также из определения => если t1 ,x₁,…,x_n+tX, sS и если A_s(x₁,…,x_n+t)=y₁,…,y_n+t, то y_n+i=_А,n(x_i,…,x_n+i) i , => по определению функции памяти а)- выполнено, кроме того  состояние автомата А эквивалентно с задержкой n  состоянию R₀(_А,n), т.е. выполнено б); в): пусть h, f- функции переходов и выходов => x₁,…,x_n => h(_A,n(x₁,…,x_n),x_n+1)=h([h(s, x₁,…,x_n+1)]_~,x_n+1)=[h(s,x₁,…,x_n+1)]_~=_A,n(x₂,…,x_n+1),

f(_A,n(x₁,…,x_n),x_n+1)=f(h(s,x₁,…,x_n),x_n+1)=_А,n(x₁,…,x_n+1)=> -гомоморфизм. т.к. гомоморфный образ сильносвязного автомата сильносвязен, а ПЛЗ- сильносвязна => все состояния в образе- существенны, т.е. _A,n(Xⁿ) ^[c] Наоборот: Пусть [s]_~( )^[c], т.е. s- существенное состояние, то по определению существенного состояния: sS; x₁,…,x_nX: [s]_~=[h(s₁,(x₁,…,x_n))]_~=_A,n(x₁,…,x_n) => _A,n(Aⁿ)( )^[c], т.е. _A,n(Aⁿ)=( )^[c].

Утверждение (о единственности ПЛЗ): пусть hN₀; _i: Xⁿ⁺¹Y, i=1,2; и некоторое состояние R₀(₁) эквивалентно некоторому состоянию R₀(₂) => ₁=₂ (т.е. R₀()- единственная ПЛЗ, которая представляет некоторый автомат самовосстановления А). Доказательство: пусть они эквивалентны с задержкой к т.е. s₁ s₂, тогда (x₁...x_n, x_n+1) = (x₁...x_n, x_n+1) т.к. после к-того такта появляются эквивалентные состояния по условию.

Следствие: для А, nN₀ следующие свойства равносильны: а) А- автомат самовосстановления с задержкой не более n; б) A R₀() для некоторого , т.е.  : Xⁿ⁺¹Y; в) A A^[c]~R₀() для некоторого .

Определение: Внутреннее самовосстановление- (т.е. вместо ~,=)- это процесс перехода из 2-х состояний: s, s в одинаковые под действием одной и той же : h(s, )=h(s, ). Для минимальных автоматов эти два понятия совпадают, т.к. у них ‘~’’=’. Если во всех предыдущих утверждениях заменить ‘~’ на ‘=’, ‘самовосстановление’ на ’внутреннее самовосстановление’, ‘’ на ‘ ’, ‘ ’ на ‘ ’, то все эти утверждения останутся верными.

Характеристики

Список файлов ответов (шпаргалок)