Дополнение к автоматной части (Ответы на экз вопросы (Криптография))

Основные определения и понятия за полный курс Теории автоматов.

Определение 1.1:

Автомат- набор из 5 объектов, А=(Х,S,Y,h,f), где X,Y,S-произвольные множества( 0)

h: S XS (1.1)

f: S XY

множества: X- входной алфавит, S- множество состояний, Y- выходной алфавит, h- функция переходов , f- функция выходов

Мы считаем, что А работает в дискретные моменты времени tN (номера тактов работы), t=1,2,..

в момент t А находится в состоянии s_tS, а на вход подается символ x_tX. Тогда А в этом такте выдает на выход символ y_tY и переходит в состояние s_t+1S, где s_t+1=h(s_t,x_t) , y_t=f(s_t,x_t) - рекуррентные соотношения(1)

Т аким образом: если на вход подается: x₁,…x_n=xXⁿ- входная последовательность, а А находится в s₁S- начальном состоянии, то на выходе появится: yYⁿ=y₁,…,y_n- выходная последовательность и А проходит последовательность состояний:

sSⁿ⁺¹=s₁,…,s_n+1 причем y_t,s_t+1- определяются по рекуррентным соотношениям(1).

S_n+1- финальное состояние. =>входная последовательность x переводит состояние s₁ в s_n+1:

A_s1(x)= y₁,…,y_n=y; => XY (1.2)

h(s₁,x)=s₁,…,s_n+1=s; => S*XS (1.3)

h(s₁,x)=s_n+1; =>S*XS (1.4)

Виды автоматов:

1.Если h, f не зависят от входных символов x, то вместо отображений (1.1) от 2-х переменных можно считать, что:

h: SS f: SY Такой автомат А=(S, Y, h, f) называется автономным (или- автомат без входов)

2. Если f(S X)=1- на выходе всегда один символ, то такой автомат А=(X, S, h) называется автоматом без выходов.

Если удалить из любого автомата f и Y, то получаем автомат без выходов.

3. Автомат со считыванием состояния: A=(X, S, S, h, e), где e(s, x)=s; fe: S XS

4. A=(S, h); h: SS

5. Автомат без памяти: A=(X, Y, f); f: XY; S=1

Определение: Если для произвольного автомата А функция выхода f(s, x) не зависит от входной переменной x : h: S XS; f: SY, то автомат называется автоматом Мура.

Определение:Если функция переходов h(s, x) не зависит существенно от входной переменной x, то автомат – внутренне автономный. Т.е. h: SS; f: S XY.

Определение:Рассмотрим произвольный автомат:Автоматное отображение автомата А при начальном состоянии sS – произвольное отображение А_s: XY, определяемое равенством (1.2), т.е. А_s(x)- выходная последовательность автомата А при начальном состоянии s и подаче на вход произвольной последовательности x

Очевидны следующие свойства:1.xXⁿ A_s(x)Yⁿ – т.е. это отображение сохраняет длины. 2. x₁, x₂X выполняется равенство: A_s (x₁,x₂)=A_s (x₁)A_h(s,x1) (x₂), т.е. говорят, что автоматное отображение начало переводит в начало.

Определение:Множество всех автоматных отображений автомата А обозначим

[A]={A_s s S}

^lA_s- ограничение автоматного отображения длины s на последовательности l.

^lA_s: X^lY^l; ^l[A]={^lA_ssS}

Определение: Автоматы А и L- эквивалентные: AL, если множество их автоматных отображений совпадает, т.е. [A]=[L] (в частности отсюда следует, что у них совпадают как входные алфавиты X, так и выходные Y.).Если считать А черным ящиком, то эквивалентные автоматы работают одинаково. Чаще всего под ключом понимают состояние автомата или часть состояний.

Определение: Частичная функция функции переходов автомата А- всякая функция h_x с фиксированным значением xX, т.е. функция, полученная фиксацией x. h_x: SS (h(s, x₀)); (В общем случае- это преобразование множества S). Всего частичных функций: X. Д ля любой последовательности x=x₁,…,x_n определим h_x: SS; h _x(s)=h(s,x)=h_xn … h_x1(s)- композиция

Определение: Полугруппа автомата А- полугруппа преобразований множества S, порожденная всеми частичными функциями переходов: G (A)=<h_x  xX>={h_x  xX}; e- тождественное преобразование= h- тождественное преобразование множ-ва S.

Определение: А-регулярный (подстановочный) автомат, если  частичная функция переходов этого автомата h_x, xX- подстановка мн-ва S => т.к. S< то полугруппа регулярного автомата- группа.

Примеры автоматов:

1. Задержка на 1 такт: X=S=Y; h(s, x)=x; f(s, x)=s

Покажем, что:  автомат добавлением задержки на 1 такт на вход или выход, сводится к автомату Мура.

При этом: А_s(x₁,…,x_n)=y₁,…y_nA_(y,s)(x₁,…,x_n)=y,y₁,…,y_n-1/

2. Регистр сдвига длины n над произвольным множеством Z с функцией обратной связи  и выходной функцией - это автомат А: R(, )=(X, Z^m, Y, h, f), где : Zⁿ XZ; : Zⁿ⁺¹Y; h((z₁,…,z_n),x)=(z₂,…,z_n,(z₁,…,z_n,x));

f((z₁,…,z_n),x)= (z₁,…,z_n,(z₁,…,z_n,x)).

В каждом такте содержимое ячеек сдвигается вверх: от z_n к z₁; содержимое z₁ при этом теряется.

 рекуррентная последовательность- то же самое, что и регистр R();

Теорема 1.3 (Критерий регулярности регистра сдвига)

Регистр R(, ) ненулевой длины- подстановочный  - биективна по 1-ой переменной.

Определение1.4: A=(X, S, Y, h, f)- подавтомат А, т.е. АА, если: XX ; SS ; YY; h,f- ограничения h, f на множестве S XS X; Т.е. h(s,x)=h(s,x); f(s,x)=f(s,x); (Если X=X, Y=Y, то подавтомат- внутренний);

из определения =>  подавтомат А однозначно определяется своими алфавитами X, S, Y. Обратное, вообще, неверно.

Критерий существования подавтомата А с заданными алфавитами: для  X, S, Y  подавтомат с такими алфавитами  h(SX)S , f(SX)Y (1.10)

Определение: sS- k-достижимое, k0 из множества SS если  sS, x X^k: ss под действием x

(Достижимое состояние, если k- опускается, т.е. для некоторого k оно достижимо).

Определение: s,s- связные, если они совпадают или  последовательность: s=s₁,…,s_n=s, n2, в которой s_i, s_i+1- соседние i=1,n-1 т.е.  неориентированный путьS - S'. => бинарное отношение связности - отношение эквивалентности на множ-ве S;

=> разбиение множ-ва S на пересекающиеся классы связных состояний: S= ;

Легко показать, что для алфавитов (X, S_i, Y)- выполняется критерий (1.10) подавтоматности.

Эти d подавтоматов- компоненты связности А (т.е. внутренние подавтоматы).

Определение: Автомат А- связный- если  два его состояния связны, т.е. d=1.

А- сильно связный, если любое его состояние достижимо из любого, т.е.  ориентированный путь: S - S'

Определение1.5: Гомоморфизм А ---> ^b A=(X, S, Y, h, f)- это тройка отображений (, , ):

: XX  sS, xX => (h(s,x))=h((s), (x)) (1.11)

: SS : (f(s,x))=f((s), (x)

: YY

Обозначение: (, , ): AA

Определение: Если XX, YY и ,- тождественные вложения, т.е. (x)=x, (y)=y, то это внутренний гомоморфизм: : AA ( гомоморфизм сводится к внутреннему гомоморфизму)

Определение: Если все , , - сюръективны (инъективны), то гомоморфизм- сюръективный (инъективныйвложение)

Определение:Если гомоморфизм- сюръективный и инъективный, то это изоморфизм (т.е. переобозначение алфавитов).

Определение: Образ автомата А при гомоморфизме- (, , ): АА- это подавтомат автомата А с алфавитами ((X), (S), (Y)) Т.е. для них (1.10) выполнены (следует из определения гомоморфизма)

Определение(1.7): Конгруэнция автомата А- это тройка бинарных отношений эквивалентности (₁₂₃) соответственно на множествах X, S ,Y, т.е. ₁X², ₂S², ₃Y², для которых выполняется импликация: если x₁x, s₂s, то h(s,x)₁h(s,x) и f(s,x)₃f(s,x)

Определение: Если (O, ₂, O), где О- эквивалентность, т.е. тождество, то конгруэнция- внутренняя

Определение: Ядро гомоморфизма =(, , ); AA- тройка эквивалентностей:

Ker=(₁, ₂, ₃): x₁x  (x)=(x); s₂s  (s)=(s); y₃y  (y)=(y); Из (1.11) следует, что Ker- конгруэнция автомата А.

1)гомоморфизм- 

2)конгруэнция- Ker

3)фактор-автомат- A/Ker

4)естественный гомоморфизм- _Кек

5)Ядро гомоморфизма- Ker

Определение: Гомоморфизм по состояниям- АА, где XX,- это всякое отображение :SS: (h(s,x))=h((s),x)

(В частности,  внутренний гомоморфизм- гомоморфизм по состояниям, но не наоборот, т.е. это понятие обобщает понятие внутреннего гомоморфизма)

Определение: Конгруэнция на состояниях автомата- это  бинарное отношение эквивалентности S² (на множ-ве S) : ss => h(s,x)h(s,x),  s,x. (=> Конгруэнция на состояниях обобщает понятие внутренней конгруэнции).

Определение: Конгруэнтное разбиение множ-ва S автомата А- это всякое разбиение множ-ва S: для  xX; SR S₂R: h_x(S₁)S₂

Способы задания автоматов:

A=(X, S, Y, h, f)- произвольный фиксированный автомат Функций f- Y^{SX}

1.Табличный способ

2. Графический:

3.Структурный способ