Дополнение к автоматной части
.docОсновные определения и понятия за полный курс Теории автоматов.
Определение 1.1:
Автомат- набор из 5 объектов, А=(Х,S,Y,h,f), где X,Y,S-произвольные множества(0)
h: SXS (1.1)
f: SXY
множества: X- входной алфавит, S- множество состояний, Y- выходной алфавит, h- функция переходов , f- функция выходов
Мы считаем, что А работает в дискретные моменты времени tN (номера тактов работы), t=1,2,..
в момент t А находится в состоянии stS, а на вход подается символ xtX. Тогда А в этом такте выдает на выход символ ytY и переходит в состояние st+1S, где st+1=h(st,xt) , yt=f(st,xt) - рекуррентные соотношения(1)
Таким образом: если на вход подается: x1,…xn=xXn- входная последовательность, а А находится в s1S- начальном состоянии, то на выходе появится: yYn=y1,…,yn- выходная последовательность и А проходит последовательность состояний:
sSn+1=s1,…,sn+1 причем yt,st+1- определяются по рекуррентным соотношениям(1).
Sn+1- финальное состояние. =>входная последовательность x переводит состояние s1 в sn+1:
As1(x)= y1,…,yn=y; => XY (1.2)
h(s1,x)=s1,…,sn+1=s; => S*XS (1.3)
h(s1,x)=sn+1; =>S*XS (1.4)
Виды автоматов:
1.Если h, f не зависят от входных символов x, то вместо отображений (1.1) от 2-х переменных можно считать, что:
h: SS f: SY Такой автомат А=(S, Y, h, f) называется автономным (или- автомат без входов)
2. Если f(SX)=1- на выходе всегда один символ, то такой автомат А=(X, S, h) называется автоматом без выходов.
Если удалить из любого автомата f и Y, то получаем автомат без выходов.
3. Автомат со считыванием состояния: A=(X, S, S, h, e), где e(s, x)=s; fe: SXS
4. A=(S, h); h: SS
5. Автомат без памяти: A=(X, Y, f); f: XY; S=1
Определение: Если для произвольного автомата А функция выхода f(s, x) не зависит от входной переменной x : h: SXS; f: SY, то автомат называется автоматом Мура.
Определение:Если функция переходов h(s, x) не зависит существенно от входной переменной x, то автомат – внутренне автономный. Т.е. h: SS; f: SXY.
Определение:Рассмотрим произвольный автомат:Автоматное отображение автомата А при начальном состоянии sS – произвольное отображение Аs: XY, определяемое равенством (1.2), т.е. Аs(x)- выходная последовательность автомата А при начальном состоянии s и подаче на вход произвольной последовательности x
Очевидны следующие свойства:1.xXn As(x)Yn – т.е. это отображение сохраняет длины. 2. x1, x2X выполняется равенство: As (x1,x2)=As (x1)Ah(s,x1) (x2), т.е. говорят, что автоматное отображение начало переводит в начало.
Определение:Множество всех автоматных отображений автомата А обозначим
[A]={As sS}
lAs- ограничение автоматного отображения длины s на последовательности l.
lAs: XlYl; l[A]={lAssS}
Определение: Автоматы А и L- эквивалентные: AL, если множество их автоматных отображений совпадает, т.е. [A]=[L] (в частности отсюда следует, что у них совпадают как входные алфавиты X, так и выходные Y.).Если считать А черным ящиком, то эквивалентные автоматы работают одинаково. Чаще всего под ключом понимают состояние автомата или часть состояний.
Определение: Частичная функция функции переходов автомата А- всякая функция hx с фиксированным значением xX, т.е. функция, полученная фиксацией x. hx: SS (h(s, x0)); (В общем случае- это преобразование множества S). Всего частичных функций: X. Для любой последовательности x=x1,…,xn определим hx: SS; hx(s)=h(s,x)=hxn…hx1(s)- композиция
Определение: Полугруппа автомата А- полугруппа преобразований множества S, порожденная всеми частичными функциями переходов: G(A)=<hx xX>={hx xX}; e- тождественное преобразование= h- тождественное преобразование множ-ва S.
Определение: А-регулярный (подстановочный) автомат, если частичная функция переходов этого автомата hx, xX- подстановка мн-ва S => т.к. S< то полугруппа регулярного автомата- группа.
Примеры автоматов:
1. Задержка на 1 такт: X=S=Y; h(s, x)=x; f(s, x)=s
Покажем, что: автомат добавлением задержки на 1 такт на вход или выход, сводится к автомату Мура.
При этом: Аs(x1,…,xn)=y1,…ynA(y,s)(x1,…,xn)=y,y1,…,yn-1/
2. Регистр сдвига длины n над произвольным множеством Z с функцией обратной связи и выходной функцией - это автомат А: R(, )=(X, Zm, Y, h, f), где : ZnXZ; : Zn+1Y; h((z1,…,zn),x)=(z2,…,zn,(z1,…,zn,x));
f((z1,…,zn),x)= (z1,…,zn,(z1,…,zn,x)).
В каждом такте содержимое ячеек сдвигается вверх: от zn к z1; содержимое z1 при этом теряется.
рекуррентная последовательность- то же самое, что и регистр R();
Теорема 1.3 (Критерий регулярности регистра сдвига)
Регистр R(, ) ненулевой длины- подстановочный - биективна по 1-ой переменной.
Определение1.4: A=(X, S, Y, h, f)- подавтомат А, т.е. АА, если: XX ; SS ; YY; h,f- ограничения h, f на множестве SXSX; Т.е. h(s,x)=h(s,x); f(s,x)=f(s,x); (Если X=X, Y=Y, то подавтомат- внутренний);
из определения => подавтомат А однозначно определяется своими алфавитами X, S, Y. Обратное, вообще, неверно.
Критерий существования подавтомата А с заданными алфавитами: для X, S, Y подавтомат с такими алфавитами h(SX)S , f(SX)Y (1.10)
Определение: sS- k-достижимое, k0 из множества SS если sS, x Xk: ss под действием x
(Достижимое состояние, если k- опускается, т.е. для некоторого k оно достижимо).
Определение: s,s- связные, если они совпадают или последовательность: s=s1,…,sn=s, n2, в которой si, si+1- соседние i=1,n-1 т.е. неориентированный путьS - S'. => бинарное отношение связности - отношение эквивалентности на множ-ве S;
=> разбиение множ-ва S на пересекающиеся классы связных состояний: S=;
Легко показать, что для алфавитов (X, Si, Y)- выполняется критерий (1.10) подавтоматности.
Эти d подавтоматов- компоненты связности А (т.е. внутренние подавтоматы).
Определение: Автомат А- связный- если два его состояния связны, т.е. d=1.
А- сильно связный, если любое его состояние достижимо из любого, т.е. ориентированный путь: S - S'
Определение1.5: Гомоморфизм А ---> b A=(X, S, Y, h, f)- это тройка отображений (, , ):
: XX sS, xX => (h(s,x))=h((s), (x)) (1.11)
: SS : (f(s,x))=f((s), (x)
: YY
Обозначение: (, , ): AA
Определение: Если XX, YY и ,- тождественные вложения, т.е. (x)=x, (y)=y, то это внутренний гомоморфизм: : AA ( гомоморфизм сводится к внутреннему гомоморфизму)
Определение: Если все , , - сюръективны (инъективны), то гомоморфизм- сюръективный (инъективныйвложение)
Определение:Если гомоморфизм- сюръективный и инъективный, то это изоморфизм (т.е. переобозначение алфавитов).
Определение: Образ автомата А при гомоморфизме- (, , ): АА- это подавтомат автомата А с алфавитами ((X), (S), (Y)) Т.е. для них (1.10) выполнены (следует из определения гомоморфизма)
Определение(1.7): Конгруэнция автомата А- это тройка бинарных отношений эквивалентности (123) соответственно на множествах X, S ,Y, т.е. 1X2, 2S2, 3Y2, для которых выполняется импликация: если x1x, s2s, то h(s,x)1h(s,x) и f(s,x)3f(s,x)
Определение: Если (O, 2, O), где О- эквивалентность, т.е. тождество, то конгруэнция- внутренняя
Определение: Ядро гомоморфизма =(, , ); AA- тройка эквивалентностей:
Ker=(1, 2, 3): x1x (x)=(x); s2s (s)=(s); y3y (y)=(y); Из (1.11) следует, что Ker- конгруэнция автомата А.
1)гомоморфизм-
2)конгруэнция- Ker
3)фактор-автомат- A/Ker
4)естественный гомоморфизм- Кек
5)Ядро гомоморфизма- Ker
Определение: Гомоморфизм по состояниям- АА, где XX,- это всякое отображение :SS: (h(s,x))=h((s),x)
(В частности, внутренний гомоморфизм- гомоморфизм по состояниям, но не наоборот, т.е. это понятие обобщает понятие внутреннего гомоморфизма)
Определение: Конгруэнция на состояниях автомата- это бинарное отношение эквивалентности S2 (на множ-ве S) : ss => h(s,x)h(s,x), s,x. (=> Конгруэнция на состояниях обобщает понятие внутренней конгруэнции).
Определение: Конгруэнтное разбиение множ-ва S автомата А- это всякое разбиение множ-ва S: для xX; SR S2R: hx(S1)S2
Способы задания автоматов:
A=(X, S, Y, h, f)- произвольный фиксированный автомат Функций f- YSX
1.Табличный способ
2. Графический:
3.Структурный способ
4. Задание автоматным отображением
Автоматы, у которых входные алфавиты совпадают- сравнимые.
Определение 2.1: Состояния sS, sS- l-эквивалентные- т.е. ss, если выходные последовательности при начальных состояниях s и s, соответственно, всегда совпадают на длине l: As()=As() Xl; Если ss для l, то s и s- эквивалентны, т.е. s~s;
Определение 2.3:Фактор-автомат: =A/~=(X, S/~, Y, , )- приведенная форма автомата А, а число (А)=S/~-приведенный вес А (число нетривиальных состояний А). Если (А)=S ‘~’=’’=0, то А- минимальный (приведенный)
(у которого нет различных эквивалентных состояний). Число неэквивалентных состояний- число отображений автомата- S/~=[A]; S/~=l[A]
Определение 2.6: Min lN0: s,sS из условия ss следует: s~s (т.е. =~)- длина (степень) различимости: (A).
Диаметр сильносвязного автомата- число d(A)=max{l(s1,s2)s1,s2S}, Где l(s1,s2)- минимальная длина входной последовательности, переводящей s1s2 (l(s1,s2)=0), т.е. минимальный путь из вершины s1 в вершину s2 в графе автомата А.
Определение 2.12: A=(X, S, Y, h, f)- представляется автоматом А=(X, S, Y, h, f) (или А представляет А), если XX, sS sS: As()=As() X*
Если А представляет А и А представляет А, то А~А, т.е. автоматы работают одинаково. X=X; Yf(S,X)=f(S,X)Y, т.е. Y=Y- т.е. подразумеваем для эквивалентных автоматов.
Определение 2.15: A и A- l-эквивалентные: AA- если sS sS: ss и наоборот, АА l[A]=l[A]
Определение 2.30: Состояния sS, sS- эквивалентные с задержкой k: ss, если для любых входных последовательностей 1Xk и X* выходные последовательности этих автоматов: As(1,), As(1,)- совпадают, начиная с (k+1) знака или, другими словами: h(s, 1)~h(s,1), 1Xk.
Определение 2.32: Минимальное l, при котором =- задержка эквивалентности А- (А).
Определение 2.37:Минимальное kN0: для А ==-задержка совпадения А: (A)
Определение 2.38:Гомоморфизм (, , ): AA- изоморфизм с задержкой. Если , - биекции (как у любого изоморфизма), - сюръективно и sS -1(s) все состояния в полном прообразе совпадают с задержкой.
Определение 4.14: A- левый (правый) обратный к А- если sS sS: As(As())=,X* (As (As())=, yY*)
Определение: обратимый если он имеет и левый и правый обратные.
Определение: инъективный (сюръективный) если все его автоматные отображения инъективны (сюръективны).
Определение: биективный, если он инъективный и сюръективный.
Определение 4.22: А- автомат без потери информации (БПИ), если s,sS; , X* справедлива импликация:
s~s, h(s)=h(s), As()=As() => = ;
Определение 4.23: Состояние s автомата А- состояние с потерей информации, если 2 различные входные последовательности , для которых h(s)=h(s), As()=As();
Определение: Автомат – автомат БПИ-1, если он инъективен, т.е. s~s, As()=As() => = (т.е. в определении 4.22 удалить 2-ую эквивалентность).
Определение: А- автомат БПИ-2, если в определении 4.22 удалить 1-ую эквивалентность.
Определение 4.32: : YbXa+1Y; a,bN0 определим автомат: M()=(X, YbXa, Y, h, f), h((y1,…,yb,x1,…,xa),x)=(y1,…,yb,(y1,…,yb,x1,…,xa,x),x2,…,xa,x);
f((y1,…,yb,x1,…,xa),x) =(y1,…,yb,x1,…,xa,x). В частности, при b=0 M()=R0()- проходная линия задержки длины a. При а=0 M()=R()
Определение 4.33: Функция памяти А- всякая функция : sS, =x1,…,xtXt, t1+max{a,b}; As()=y1,…,yt => yt=(yt-b,…,yt-1,xt-a,…,xt) => Память автомата А- число m(A)=max{a,b};
Если , то m(A)= иначе m(А)<; Если m(A)<, то А- автомат с конечной памятью
Определение 4.37: Входная последовательность X*- диагностическая для А, если s,sS справедлива импликация: As()=As() => s~s и последовательность - установочная, если Aa()=As() => h(s, )~h(s,) (эквивалентность финальных).
Определение 4.43: Длина единственности- l(A)- минимальное lN0: входная последовательность Xl- диагностическая для А. l(A)=, если таких l не существует.
Определение: Если в КС были искажены k знаков, то в случае, когда в последовательности число искажений >k => произошло распространение искажений, иначе- искажения не распространились.
] : X*Y*, сохраняя длины, т.е. (Xl)Yl, l (,)- количество номеров несовпадающих членов в этих последовательностях, т.е. (,)= {i=xi xi }, ,Xl ((,) - метрика Хемпинга)
Определение4.59 : Отображение , сохраняющее длины слов- распространяющее искажения не более чем в k раз, если lN; ,Xl выполняется неравенство: ((),())k*(,) ; Если k=1 => - отображение, нераспространяющее искажений.
Шифр колонной замены- порожденный множ-вом подстановок {gl,tl,tN, tl}, gl,tG(X)Sx- (симметрическая группа подстановок), называется отображение : X*X*, определяемое по формуле:
(x1,…,xl)= gl,1(x1),…,gl,l(x1); (()())=(,)
Шифр перестановки- порожденный множ-вом подстановок {pllN}, plSl, преобразование : X*X*, определяется равенством: (x1,…,xl)=,…,; ((),())=(,); {=> - тоже не распространяет искажений}
Определение 4.65: А- не распространяющее искажений по , если для sS, lN, =(x1,…,xl), =(x1,…,xl)Xl: xixi, i выполняется неравенство: (As(),As())(,) {При =x2 => автомат А- нераспространяющий искажений}
Самовосстановление в автоматах: - процесс перехода этого автомата из произвольных 2-х или более состояний в эквивалентные (т.е. в один и тот же класс эквивалентности) под действием одной и той же входной последовательности. Чем больше вероятность такого события- тем устойчивее автомат к случайным сбоям (во входной последовательности, в функции перехода…)
Определение: Матрица переходных состояний k-грамм- матрица вида Bk=(P(), которая определяется так: - матрица размера SkSk ; - строки и столбцы- занумерованы векторами состояний длины k: k={}; - на пересечении строки =(s1,…,sk) и столбца =(s1,…,sk) стоит вероятность: P()=X-1{xXh(si,x)=si)} i,k.
Определение: (A): = -l0, a); -, б); - задержка самовосстановления в А
Определение 4.68: А- самовосстановления с задержкой n, если h(s,)~h(s,) s,sS, Xn, причем, n- минимальное такое. Здесь n- задержка самовосстановления автомата А.
Определение 4.71: Два автомата: A и A с одним и тем же входным алфавитом- эквивалентные с задержкой n: AA, если для s автомата А s автомата А: ss и наоборот.
Определение: Внутреннее самовосстановление- (т.е. вместо ~,=)- это процесс перехода из 2-х состояний: s, s в одинаковые под действием одной и той же : h(s,)=h(s,)
Определение 4.75 (из определения 4.68): А- внутренний самовосстанавливающийся с задержкой n, если h(s,)=h(s,) s, sS; Xn, причем: n- минимальное такое, что: =1- все состояния А совпадают с задержкой и =n – задержка совпадения.