Презентация4.Эквивалентность автоматов

1. Минимизация и эквивалентность автоматов

2. Проблема кодировки состояний

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

3. Проблема кодировки состояний

Различное кодирование может влиять на
надежность устройства, скорость его переключения
и т.д.
Проблема оптимального кодирования состояний
при различных критериях оптимальности до сих
пор остается актуальной.
Существуют некоторые традиционные подходы,
позволяющие заменять одно множество состояний
другим – оптимальным или минимальным в том
или ином смысле.
Такая замена осуществляется на основе понятия
«эквивалентности».

4. Расширенные функции автомата

X*- множество входных последовательностей
Y* - множество выходных последовательностей.
Пусть A = {X, S, Y, δ, λ}- конечный автомат.
Расширенными функциями переходов и выходов автомата
A называются функции
δ*:S X* S
λ*:S X* Y*
( s, xi xi ...xi ) (.... ( ( s, xi ), xi )...), xi )
1
2
n
1
2
n
( s, xi xi ...xi ) ( s, xi ) ( ( s, xi ), xi ),...., ( ( s, xi ...xi ), xi )
1
2
n
1
1
2
1
n 1
n

5. Эквивалентность состояний

Состояние si автомата А и состояние sj автомата B эквиваленты
(si = sj), если автоматы А и B, находясь в состояниях si и sj
соответственно, под воздействием любой входной
последовательности выдают одинаковые выходные
последовательности, т.е.
( X *) * ( si , ) * ( s j , )
Если состояния не эквиваленты, но их называют
различимыми. si ≠ sj
Обозначения A и B могут относиться к одному и тому же
автомату.
Данное определение не является конструктивным, так как не
дает нам процедуры выяснения того, являются два состояния
эквивалентными или нет.

6. Эквивалентность состояний

Эквивалентность состояний обладают
свойством рефлективности (si=si),
свойством симметричности (если si=sj, то sj=si),
свойством транзитивности (если si=sj и sj=sk, то si=sk).
Следовательно, эквивалентность состояний может
рассматриваться как обычное отношение
эквивалентности, которое применимо к множествам
любой мощности.
Различимость состояний не обладает свойствами
рефлективности и транзитивности, следовательно,
может относиться только к парам состояний.

7. Проблема определения эквивалентности состояний

В некоторых случаях эквивалентность или
различимость двух состояний одного и того же
автомата могут быть установлены исследованием
таблицы переходов данного автомата, а именно
справедливы следующие утверждения.
Если строки si и sj в таблице выходов автомата
различаются, то si sj
Если строки si и sj в таблице переходов-выходов автомата
совпадают, то si=sj.
Если строки si и sj в таблице переходов-выходов автомата
становятся одинаковыми при замене каждого
обозначения si на sj (или наоборот), то si=sj.

8. Пример

9. Пример

Строки 1 и 5 одинаковы
1 и 5 эквивалентны,
Строки 2 и 6 становятся одинаковыми, если каждую цифру
два заменить на цифру 6
2 и 6 эквивалентны.
Подтаблица выходов
ни одно из состояний 1,5,4,8 не
может быть эквивалентным какому-либо состоянию из
множества 2, 3, 6, 7.

10. k-эквивалентность состояний

Состояния si автомата A и sj автомата B называются
k – эквивалентными (si=ksj), если при приложении к
автомату A, находящемуся в состоянии si и к
автомату B, находящемуся в состоянии sj входной
последовательности длины k они вырабатывают
одинаковые выходные последовательности.
( X * , | | k ) * ( si , ) * ( s j , )
Если состояния si и sj не являются k-
эквивалентными, то они называются kразличимыми (si ksj).
Обозначения А и В могут относиться к одному
автомату.

11. k-эквивалентность состояний

k-эквивалентные состояний обладают
свойством рефлективности (si=ksj),
свойством симметричности (если si=ksi, то sj=ksi),
свойством транзитивности (если si=ksj и si=kst, то si=kst).
Следовательно, k-эквивалентность состояний может
рассматриваться как обычное отношение
эквивалентности, которое применимо к множествам
любой мощности.
k-различимость состояний не обладает свойствами
рефлективности и транзитивности, следовательно,
может относиться только к парам состояний.

12. Свойства k-эквивалентности

Если два состояния являются
k эквивалентными, то они являются и
l эквивалентными для каждого l<=k.
Если два состояния являются
k различимыми, то они являются и
l различимыми для каждого l>=k.

13. k-приемники состояний

Состояние, в которое переходит состояние si при
подачи входной последовательности длины k,
называется k-м приемником состояния si по
отношению к этой последовательности.
Если состояния si и sj являются k-эквивалентными
и если их k-ые приемники по отношению к любой
входной последовательности длины k являются
эквивалентными, то si=sj.

14. k-приемники состояний

Если состояния si и sj
являются эквивалентными,
то их k-ые приемники по
отношению к любой
входной
последовательности длины
k и для любого k являются
эквивалентными.
Свойства k-приемников могут быть использованы для
установления эквивалентности одних состояний, когда
эквивалентность других уже установлена.

15. Пример

Пусть 1, 5 – эквиваленты
и 3, 7 - эквиваленты
Тогда 4,8 - эквивалентны, т.к.
4 и 8 являются 1-эквивалентными,
их первые приемники
1,5 и 3,7 – эквиваленты

16. Пример

Если 4, 8 эквивалентны, то состояния в парах
1,5; 2,6; 3,7 должны быть также эквивалентными, т.к. они
представляют собой пары соответствующих состояний на
путях, начинающихся состояниями 4 и 8.

17. k-эквивалентное разбиение автомата

k-эквивалентным разбиением автомата (Pk)
называется разбиение его на классы
k эквивалентности ( k1, k2, k3,…), такие что
все стояния, принадлежащие одному классу должны быть
k-эквивалентными.
все состояния, принадлежащие разным классам должны
быть k-различимыми.
Cостояния, принадлежащие к одному классу
называются смежными
Состояния, принадлежащие к различным классам,
называются разобщенными

18. Пример

P2:
21={1,3,5,7,8}, 22={2,4,6}, 23={9}.

19. Свойства k-эквивалентного разбиения

Ни одно состояние не может принадлежать
одновременно двум k-эквивалентным классам,
поскольку это обозначало бы, что это состояние
является k-различимым по отношению к самому
себе.
Общее число состояний в Pk равно общему числу
состояний в автомате.
k-эквивалентное разбиение автомата единственно
Состояния, разобщенные в Pk являются
разобщенными и в Pk+1.

20. Свойства k-эквивалентного разбиения

Если автомат имеет два различимых, но k-
эквивалентных состояния, то он также имеет
два состояния, которые являются kэквивалентными, но k+1 различимыми.
Pk+1 является собственным разделением Pk,
если не во всех класса Pk смежные состояния
являются эквивалентными. В противном
случае Pk и Pk+1 совпадают.
Если Pk = Pk+1, то Pk = Pi для любого i>k.

21. Эквивалентное разбиение автомата

K-эквивалентное разбиение автомата (Pk)
называется эквивалентным разбиением автомата
(P), если во всех классах этого разбиения смежные
состояния эквиваленты.
Из свойств Pk следует, что P является наиболее
детальным разбиением Pk, которое может быть
получено последовательным построением Pk,
k=1,2,3… до тех пор, пока не получим разбиение
совпадающее с предыдущем.

22. Метод построения эквивалентного разбиения

Строим P1: состояния являются смежными в P1,
если для каждого входного сигнала они дают
одинаковы выходные сигналы.
Строим Pk+1 по Pk (k 1).
Пары смежных состояний в Pk, которые при любом
входном сигнале переходят в смежные состояния в Pk
представляют собой k-эквивалентные состояния,
первые приемники которых по отношению к любому
входному символу являются k-эквивалентными.
Поэтому такие смежные состояния являются (k+1)эквивалентными и должны быть смежными в Pk+1.

23. Метод построения эквивалентного разбиения

Пары смежных состояний в Pk+1, которые при
некотором водном сигнале переходят в разобщенные
состояния в Pk, представляют собой k-эквивалентные
состояния, первые приемники которых по отношению
к некоторому входному символу являются kразличимыми. Поэтому такие смежные состояния
являются (k+1)-различимыми и должны быть
разобщены в Pk+1.
Два разобщенных состояния в Pk должны быть
разобщены и в Pk+1.
Одно элементные классы в Pk автоматически
включаются в Pk+1.
Если Pk+1=Pk то P=Pk+1.

24. Метод Pk таблиц

За исключение простейших случаев, процесс определения
эквивалентно разбиения автомата по таблице или графу,
практически не возможен. Однако он возможен путем
систематического построения так называемых таблиц Pk.
Таблица Pk заданного автомата представляет собой таблицу
переходов со следующими отличиями:
Если состояния {si1, si2,…, sir} представляют собой класс Pk,
то строки si1, si2,…, sir группируются вместе и каждая группа
строк отделяется линией от соседних строк.
Порядок групп в таблице и порядок строк в каждой группе
произвольны.

25. Метод Pk таблиц

Строки, принадлежащие к одной группе, и
следовательно, представляющие класс kэквивалентности, будем называть смежными
строками, а строки, принадлежащие к разным
группами будем называть разобщенными строками.
Добавляется столбец , в котором указывает
произвольное обозначение групп в таблице Pk.
Каждое значение состояния в ячейке снабжается
индексом, указывающим группу, которой относится
данное значение.

26. Пример

P1

27. Пример

P1
Пример
P2

28. Пример

P2
Пример
P3

29. Пример

P3
Пример
P4

30. Пример

31. Минимальная форма автомата

s1 , s 2 ,...s n
Минимальная форма автомата
Заметим, что в качестве обозначений
можно,
например, выбрать обозначения классов эквивалентности из
последней построенной Pk-таблицы.

32. Пример

В минимальной форме любого автомата все состояния различимы.

33. Эквивалентность автоматов

Автоматы
А = {X, YA, SA,δA, λA, s0A} и В= {X, YB, SB,δB, λB, s0B}
с одинаковым входным алфавитом X называются
эквивалентами, если каждому состоянию автомата
А соответствует по крайней мере одно
эквивалентное ему состояние автомата B, а каждому
состоянию автомата B, соответствует по крайней
мере одно эквивалентное ему состояние автомата A.
Если автоматы А и В не эквивалентны, то они
различимы.

34. Эквивалентность автоматов

Два автомата А и B эквивалентны, если наблюдая
их выходные реакции нельзя отличить автомат А в
любом из его состояний или автомата B любом из
его состояний, т.е.
( X *) * (s0 A , ) * (s0 B , )
Автоматы А и В являются различимыми, если
имеется по крайней мере одно состояние автомата
А, которому не эквивалентно ни одно состояние
автомата B или наоборот, иными словами, если
автоматы выдают различные реакции на какуюлибо входную последовательность, т.е.
( X *) * (s0 A , ) * ( s0 B , )

35. Эквивалентность автоматов

Эквивалентность автоматов обладают
свойством рефлективности (A=A),
свойством симметричности (если A=B, то B=A)
свойством транзитивности (если A=B и B=C, то A=C).
Следовательно, эквивалентность автоматов может
рассматриваться как обычное отношение
эквивалентности, которое применимо к множествам
любой мощности.
Различимость автоматов не обладает свойствами
рефлективности и транзитивности, следовательно,
может относиться только к парам автоматов.

36. Явная эквивалентность

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

37. Пример

А1
А2
Cостояние 1 автомата A1 и состояние 1 автомата А2 явно эквивалентны
Состояние 2 автомата A1 и состояние 2 автомата А2 явно эквивалентны
Состояние 3 автомата А1 явно эквивалентно состоянию 1 автомата А1,
а следовательно и состоянию 1 автомата А2.
Следовательно, автоматы эквивалентны.

38. Пример

А2
А3
Cостояние 1 автомата A2 и состояние 1 автомата А3 явно эквивалентны
Состояние 2 автомата A2 и состояние 2 автомата А3 явно эквивалентны
Однако пары состояний {1,3} и {2,3} явно различимы и следовательно
состояние 3 автомата А3 не имеет эквивалентному ему состояния в
автомате А2. Следовательно автоматы А2 и А3 различимы.

39. Эквивалентность автоматов

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

40. Достижимость состояний

Пусть А = {X, Y, S,δ, λ, s0} – конечный автомат. Состояние
s S называется достижимым, если
( X *) (s0 , x) s
иными словами, если автомат под воздействием какой-либо
входной цепочки попадает из начального состояние в это
состояние.
Состояние s S называется недостижимым, если
( X *) ( s0 , x) s
иными словами, если не существует входной
последовательности при подачи которой, автомат может
перейти из начального состояния в это состояние.

41. Достижимость

Множество достижимых состояний конечного
автомата строится с помощью алгоритма,
основанного на индукции.
Шаг 0. Обозначим множество Q0={s0}.
Шаг i. Строится множество Qi состояний, достижимых из
начального при подачи входной цепочки длины не
более i. Очевидно, что
Qi 1 Qi ( s Q x X ( s, x))
причем не более чем |S| шагов будет построено
множество Qk=Qk+1, которое будет включать все
достижимые состояния автомата.

42. Пример

Q0={s0}, Q1={s0,s1}, Q2={s0,s1, s4}, Q3={s0,s1, s4, s3}, Q4={s0,s1, s4, s3}.
Следовательно, множество достижимых состояний
автомат {s0,s1, s4, s3}, причем они достижимы при подаче
входной последовательности длины не более трех.
Состояние s2 - недостижимое.
Недостижимые состоянии представляют собой узлы
графа, в которые нет ни одной входящей дуги.

43. Прямое произведение автоматов

Прямым произведением конечных автоматов А =
{X, YA, SA,δA, λA, s0A} и В= {X, YB, SB,δB, λB, s0B} с
одинаковым входным алфавитом X называется
автомат
,
А В = {X, YA YB, SA SB,δA B, λA B, (s0A, s0B)}, где
( s A S A )( s B S B )( x X ) A B ((s A , s A ), x) ( A (s A , x), B (s B , x))
( s A S A )( sB S B )( x X ) A B ((s A , s A ), x) ( A (s A , x), B (sB , x))

44. Прямое произведение автоматов

Прямое произведение двух конечных автоматов – это два
независимо действующих конечных автомата, синхронно
работающих на одном входе.

45. Пример

A
Пример
A B
B

46. Пример

47. Теорема Мура

Два конечных автомата А={X,YA,SA,δA, λA, s0A}
и В={X, YB, SB,δB, λB, s0B} с одинаковым
входным алфавитом являются эквивалентными
тогда и только тогда, когда для любого
достижимого состояния (sA, sB) в их прямом
произведении А В справедливо:
( x X ) A (s A , x) B (sB , x)

48. Эквивалентность автоматов Мили и Мура

Каждому автомату Мили, соответствует
эквивалентный ему автомат Мура.
Каждому автомату Мура, соответствует
эквивалентный ему автомат Мили.
Классы автоматов Мили и Мура
эквивалентны

49. Построение автомата Мили по автомату Мура

Из совмещенной
таблицы автомата
Мили выделить
таблицу выходов, в
которой каждому
состоянию будет во
всех строках (x)
соответствовать одно и
тоже значение
выходного сигнала.

50. Построение автомата Мили по автомату Мура

Если автомат задан графом, то обозначение
выходного сигнала выносится из узла и добавляется
на каждую входящую в состояние дугу.

51. Построение автомата Мура по автомату Мили

Если автомат при входе в состоянии s может
генерировать k различных выходных сигналов
{yi1,yi2….,yik}, то состояние s расщепляется на k
состояний {(s1/yi1)(s2/yi2),…,(sk/yik)}.
Если для состояния s автомат Мили и некоторого
входного сигнала xt
δ(s, xt)=p,
λ(s, xt)=yt,
то для эквивалентного ему автомата Мура должно
быть справедливо
δ((s1/yi1), xt)=(pj1/yt)
δ((s2/yi2), xt)= (pj2/yt)
………….
δ((sk/yik), xt)= (pjm/yt)

52. Построение автомата Мура по автомату Мили

Состояние p расщепляется не состояние
(p0/0) и (p1/1)
Состояние q расщепляется не состояние
(q0/0) и (q1/1)
Состояние r обозначается (r0/1)
Т.к. δ(p, a)=p, λ (p, a)=0, то δ((p0/0), a)=(p0/0),
δ((p1/1), a)=(p0/0),
Т.к. δ(p, b)=q, λ (p, b)=1, то δ((p0/0), b)=(q1/1),
δ((q1/1), b)=(q1/1),
Т.к. δ(q, a)=r, λ (q, a)=0, то δ((q0/0), a)=(r0/0),
δ((q1/1), a)=(r0/0),
Т.к. δ(q, b)=q, λ (q, b)=0, то δ((q0/0), b)=(q0/0),
δ((q1/1), b)=(q0/0),
Т.к. δ(r, a)=p, λ (r, a)=1, то δ((r0/0), a)=(p1/1)
Т.к. δ(r, b)=q, λ (r, a)=1, то δ((r0/0), b)=(q1/1)