Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.13. Простые безусловные установочные эксперименты

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

Алгоритм 4.5. Даны автомат М и его множество допустимых начальных состояний требуется найти конечное состояние М с помощью кратчайшего простого безусловного эксперимента. (1) Строим установочное дерево для М и . Выбираем любую установочную последовательность описываемую деревом (3) Составляем перечень реакций и состояний в которые соответственно переходят при подаче (4) Прилагаем и фиксируем реакцию. Конечное состояние есть состояние для которого реакция, внесенная в перечень совпадает с зафиксированной реакцией.

Алгоритм 4,5 может быть продемонстрирован на примере автомата АП (рис. 4.3) и множества допустимых начальных состояний В этом случае установочное дерево на рис. 4.16 выявляет, что минимальная установочная последовательность есть Таблица 4.11 содержит перечень

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

Таблица 4.11. Реакция

Решение установочной задачи непосредственно может быть применено к следующей задаче. Известно, что заданный автомат М есть автомат в состоянии, принадлежащем множеству или автомат в состоянии, принадлежащем множеству или автомат в состоянии, принадлежащем множеству . Желательно распознать автомат и его конечное состояние. Если предположить, что являются сравнимыми и что их таблицы переходов имеются, то указанная выше задача есть в точности установочная задача для состояний для расщепляемого автомата и множества допустимых начальных состояний В этом случае в основном предположении, что заданный автомат М является минимальным, подразумевается, что каждый автомат является минимальным и что ни одно состояние любого автомата не является эквивалентным какому-нибудь состоянию автомата

<< Предыдущий параграф Следующий параграф >>
Оглавление