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


16. Эквивалентность и различимость состояний автомата.

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

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

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

Если строки si и sj в таблице выходов автомата различаются, то si¹sj 

Если строки si и sj в таблице переходов-выходов автомата совпадают, то si=sj.

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

 


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