пользователей: 21241
предметов: 10456
вопросов: 177505
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


17. K-эквивалентность и K-различимость стояний автомата, их свойства. K-эквивалентное разбиение автомата и его свойства.

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

Свойства как в предыдущем задании.

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

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

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

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

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

Теорема. Pk+1 является собственным разделением Pk, если не во всех класса Pk смежные состояния являются эквивалентными. В противном случае Pk и Pk+1 совпадают.

Если Pk = Pk+1, то Pk = Pi  для любого i>k.

 


19.01.2016; 06:42
хиты: 21
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь