Процедура редукции Мура - Moore reduction procedure

В информатике Процедура редукции Мура это метод, используемый для Минимизация DFA.

Концепция состоит в том, чтобы начать предполагать, что каждое состояние может объединяться с любым другим состоянием, а затем разделить различимые состояния на отдельные группы, называемые разделы эквивалентности. Когда разделы эквивалентности больше не содержат различимых состояний, состояния, оставшиеся в той же группе, что и другие состояния, объединяются. Разделы эквивалентности пронумерованы по количеству шагов, которые потребовались, чтобы добраться до этой точки. 0-й раздел содержит все состояния в одной группе, 1-й раздел содержит состояния, сгруппированные по их выходы Только. В каждом разделе с этого момента есть группы, основанные на том, к какой группе из предыдущего раздела относится следующее состояние этих состояний. Процедура завершена, когда раздел п совпадает с разделом .

Состояния, различимые на kth разделы называются k-различимый состояния. Состояния, которые находятся в одной группе на kth разделы называются k-эквивалент. Обратите внимание, что состояния, которые k-эквивалентные в одной точке не обязательно эквивалентные состояния, так как они могут быть разделены на отдельные группы в более высоком разделе.

Порядок действий следующий:

  1. разделить состояния на группы, которые имеют одинаковый непосредственный выход для одного и того же текущего входа,
  2. различать состояния, следующие состояния которых находятся в разных группах,
  3. перегруппируйте состояния и повторяйте вышеуказанный шаг, пока не перестанут различаться состояния.

Смотрите также

Рекомендации

  • Ральф Лэммель; Йост Виссер; Жоао Сараива (8 октября 2008 г.). Генеративные и трансформационные методы в программной инженерии II: Международная летняя школа, GTTSE 2007, Брага, Португалия, 2-7 июля. 2007, Исправленные статьи. Springer. С. 483–. ISBN  978-3-540-88643-3.