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


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

K-эквивалентное разбиение автомата (Pk) называется эквивалентным разбиением автомата (P), если во всех классах этого разбиения смежные состояния эквиваленты.

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

Таблицы Pk строятся следующим образом. ТЕТРАДЬ!!!

 


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